On the performance of peeling algorithms

Michel Petitjean and Gilbert Saporta

Applied Stochastic Models and Data Analysis, 1992, vol. 8, issue 2, 91-98

Abstract: The peeling of a d‐dimensional set of points is usually performed with successive calls to a convex hull algorithm; the optimal worst‐case convex hull algorithm, known to have an O(n˙ Log (n)) execution time, may give an O(n˙n˙ Log (n)) to peel all the set; an O(n˙n) convex hull algorithm, m being the number of extremal points, is shown to peel every set with an O(n‐n) time, and proved to be optimal; an implementation of this algorithm is given for planar sets and spatial sets, but the latter give only an approximate O(n˙n) performance.

Date: 1992
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://doi.org/10.1002/asm.3150080204

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wly:apsmda:v:8:y:1992:i:2:p:91-98

Access Statistics for this article

More articles in Applied Stochastic Models and Data Analysis from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().