How to reduce the average complexity of convex hull finding algorithms

DOI10.1016/0898-1221(81)90059-6MaRDI QIDQ1151049zbMATH OpenOpenAlexFDO

Authors Luc 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

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

Cites work

• A fast convex hull algorithm
• A Lower Bound to Finding Convex Hulls
• A note on finding convex hulls via maximal vectors
• An efficient algorithm for determining the convex hull of a finite planar set
• Convex hulls of finite sets of points in two and three dimensions
• Die konvexe H�lle von n rotationssymmetrisch verteilten Punkten
• Divide and conquer for linear expected time
• scientific article; zbMATH DE number 3116034 (Why is no real title available?)
• scientific article; zbMATH DE number 3557226 (Why is no real title available?)
• scientific article; zbMATH DE number 3563431 (Why is no real title available?)
• scientific article; zbMATH DE number 3224041 (Why is no real title available?)
• scientific article; zbMATH DE number 3290003 (Why is no real title available?)
• scientific article; zbMATH DE number 3349081 (Why is no real title available?)
• scientific article; zbMATH DE number 3354336 (Why is no real title available?)
• On the Average Number of Maxima in a Set of Vectors and Applications
• On the complexity of finding the convex hull of a set of points
• On the Distribution of the Number of Admissible Points in a Vector Random Sample
• On the identification of the convex hull of a finite set of points in the plane
• Subadditive ergodic theory
• Sur la distribution limite du terme maximum d'une série aléatoire
• The convex hull of a random set of points
• Uniform convergence of the empirical distribution function over convex sets
• �ber die konvexe H�lle von n zuf�llig gew�hlten Punkten
• �ber die konvexe H�lle von n zuf�llig gew�hlten Punkten. II

Cited in

(10)

• 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
• Randomized quickhull
• On the oscillation of the expected number of extreme points of a random set
• Random convex hulls and extreme value statistics

This page was built for publication: How to reduce the average complexity of convex hull finding algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1151049)