How to reduce the average complexity of convex hull finding algorithms

DOI10.1016/0898-1221(81)90059-6zbMath0456.68080OpenAlexW2036621183MaRDI QIDQ1151049

Luc P. Devroye

Publication date: 1981

Published in: Computers \& Mathematics with Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0898-1221(81)90059-6

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Convex sets in (n) dimensions (including convex hypersurfaces) (52A20) Random convex sets and integral geometry (aspects of convex geometry) (52A22) Discrete mathematics in relation to computer science (68R99)

Related Items

Average complexity of a gift-wrapping algorithm for determining the convex hull of randomly given points, A note on linear expected time algorithms for finding convex hulls, On the computer generation of random convex hulls, Moment inequalities for random variables in computational geometry, Convex hulls of samples from spherically symmetric distributions, Randomized quickhull, Random convex hulls and extreme value statistics, On the oscillation of the expected number of extreme points of a random set, Random convex hulls in a product of balls, Maximal and minimal balls

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on finding convex hulls via maximal vectors
• On the complexity of finding the convex hull of a set of points
• Subadditive ergodic theory
• Uniform convergence of the empirical distribution function over convex sets
• A fast convex hull algorithm
• Divide and conquer for linear expected time
• An efficient algorithm for determining the convex hull of a finite planar set
• On the identification of the convex hull of a finite set of points in the plane
• Sur la distribution limite du terme maximum d'une série aléatoire
• A Lower Bound to Finding Convex Hulls
• Convex hulls of finite sets of points in two and three dimensions
• On the Average Number of Maxima in a Set of Vectors and Applications
• On the Distribution of the Number of Admissible Points in a Vector Random Sample
• [https://portal.mardi4nfdi.de/wiki/Publication:5331598 �ber die konvexe H�lle von n zuf�llig gew�hlten Punkten. II]
• The convex hull of a random set of points
• [https://portal.mardi4nfdi.de/wiki/Publication:5588965 Die konvexe H�lle von n rotationssymmetrisch verteilten Punkten]
• [https://portal.mardi4nfdi.de/wiki/Publication:5728818 �ber die konvexe H�lle von n zuf�llig gew�hlten Punkten]