How to reduce the average complexity of convex hull finding algorithms

DOI10.1016/0898-1221(81)90059-6zbMath0456.68080MaRDI 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

68Q25: Analysis of algorithms and problem complexity

52A20: Convex sets in (n) dimensions (including convex hypersurfaces)

52A22: Random convex sets and integral geometry (aspects of convex geometry)

68R99: Discrete mathematics in relation to computer science

Related Items

Randomized quickhull, On the oscillation of the expected number of extreme points of a random set, Random convex hulls and extreme value statistics, 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, Maximal and minimal balls, Random convex hulls in a product of balls, Average complexity of a gift-wrapping algorithm for determining the convex hull of randomly given points

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]