A Convex Hull Algorithm Optimal for Point Sets in Even Dimensions

Keywords

Convex hull, Output-sensitive algorithm, Orthogonal convex hull, Mathematics, Hull

References

• S C I E N C EA. W. E. E. K. L. Y. J. O U R N A L D E V O T E D T O T H E A D V A N C E, F. Science, P. U B L I S H I N G T H E O F F I C I A L

Cited by

• Moment inequalities for random variables in computational geometryLuc Devroye — 1983
• Robust and generic abstract domain for static program analyses : the polyhedral caseDuong Nguyen Que — 2010
• Average-case analysis of algorithms for convex hulls and Voronoi diagramsRex A. Dwyer — 1988
• Lower bounds for fundamental geometric problemsJeffrey Gordon Erickson, Raimund Seidel — 1996
• Binary decision diagrams and integer programmingMarkus Behle — 2007
• The Voronoi diagram of three arbitrary lines in R3Hazel Everett, Christian Gillot, Daniel Lazard — 2009
• Output-sensitive construction of convex hullsTimothy M. Chan — 1995
• Voronoi diagrams—a survey of a fundamental geometric data structureFranz Aurenhammer — 1991
• Tetrahedrizing Point Sets in Three DimensionsHerbert Edelsbrunner, F. P. Preparata, Douglas B. West — 1990
• New lower bounds for convex hull problems in odd dimensionsJeff Erickson — 1996
• Computational Geometry—A SurveyLee, Preparata — 1984
• A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedraDavid Avis, Komei Fukuda — 1991
• Derandomizing an Output-sensitive Convex Hull Algorithm in Three DimensionsBernard Chazelle, Jiřı́ Matoušek — 1995
• An efficient algorithm for construction of the power diagram from the voronoi diagram in the planeMarina L. Gavrilova, Jon Rokne — 1996
• Small-dimensional linear programming and convex hulls made easyRaimund Seidel — 1991
• In-place techniques for parallel convex hull algorithms (preliminary version)Mujtaba R. Ghouse, Michael T. Goodrich — 1991
• Euclidean minimum spanning trees and bichromatic closest pairsPankaj K. Agarwal, Herbert Edelsbrunner, Otfried Schwarzkopf — 1990
• Algorithms for high dimensional stabbing problemsDavid Avis, Mike Doskas — 1990
• An optimal algorithm for constructing the weighted voronoi diagram in the planeFranz Aurenhammer, Herbert Edelsbrunner — 1984
• Average complexity of a gift-wrapping algorithm for determining the convex hull of randomly given pointsKarl Heinz Borgwardt — 1997

Related papers

• Convex hulls of finite sets of points in two and three dimensionsF. P. Preparata, S. J. Hong — 1977
• Algorithms in Combinatorial GeometryJacob E. Goodman, Herbert Edelsbrunner — 1987
• Constructing higher-dimensional convex hulls at logarithmic cost per faceRaimund Seidel — 1986
• Applications of random sampling in computational geometry, IIKenneth L. Clarkson — 1988
• An Algorithm for Convex PolytopesDonald R. Chand, Sham S. Kapur — 1970
• Closest-point problemsMichael Ian Shamos, Dan Hoey — 1975
• The Ultimate Planar Convex Hull Algorithm?David Kirkpatrick, Raimund Seidel — 1986
• An Efficient Algorithm for Determining the Convex Hull of a Finite Planar SetRonald Graham — 1972
• An optimal convex hull algorithm in any fixed dimensionBernard Chazelle — 1993
• Linear Programming in Linear Time When the Dimension Is FixedNimrod Megiddo — 1984