A note on finding convex hulls via maximal vectors

DOI10.1016/0020-0190(80)90036-8zbMath0444.68063OpenAlexW1981507127MaRDI QIDQ1144946

Luc P. Devroye

Publication date: 1980

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(80)90036-8

zbMATH Keywords

convex hullsmaximal vectors

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Convex sets in (2) dimensions (including convex curves) (52A10) Discrete mathematics in relation to computer science (68R99)

Related Items (15)

Records, the maximal layer, and uniform distributions in monotone sets ⋮ Fast algorithms for computing the diameter of a finite planar set ⋮ On random cartesian trees ⋮ A note on linear expected time algorithms for finding convex hulls ⋮ How to reduce the average complexity of convex hull finding algorithms ⋮ Convex-hull algorithms: implementation, testing, and experimentation ⋮ Moment inequalities for random variables in computational geometry ⋮ Direct dominance of points ⋮ Evolutionarily stable strategies of random games, and the vertices of random polygons ⋮ Fast linear expected-time algorithms for computing maxima and convex hulls ⋮ On the average number of maximal in a set of vectors ⋮ Sampling-based approximate skyline calculation on big data ⋮ Random convex hulls in a product of balls ⋮ On the variance of the number of maxima in random vectors and its applications ⋮ Random polytopes in a convex polytope, independence of shape, and concentration of vertices

Cites Work

• A note on linear expected time algorithms for finding convex hulls
• 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
• 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
• ZufÄllige konvexe Polygone in einem Ringgebiet
• Sur L'enveloppe convexe des nuages de points aleatoires dans Rⁿ. I
• Unnamed Item

This page was built for publication: A note on finding convex hulls via maximal vectors