Some performance tests of convex hull algorithms

DOI10.1007/BF01934510MaRDI QIDQ1070524zbMATH OpenOpenAlexFDO

Authors D. C. S. Allison, M. T. Noga

Publication date 1984

Published in BIT (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01934510

zbMATH Keywords

computational geometrydistributive partitioninggeometric sortingplanar point distributionstwo-dimensional convex hull algorithms

Mathematics Subject Classification ID

Software, source code, etc. for problems pertaining to convex and discrete geometry (52-04) Polytopes and polyhedra (52Bxx) Convex sets in (2) dimensions (including convex curves) (52A10) Algorithms in computer science (68W99)

Recommendations

• An efficient and numerically correct algorithm for the 2D convex hull problem
• The quickhull algorithm for convex hulls
• A modification of Graham's algorithm for determining the convex hull of a finite planar set
• A modified Graham's convex hull algorithm for finding the connected orthogonal convex hull of a finite planar point set
• The Ultimate Planar Convex Hull Algorithm?

Cites work

• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• A Lower Bound to Finding Convex Hulls
• A New Convex Hull Algorithm for Planar Sets
• A fast convex hull algorithm
• A reevaluation of an efficient algorithm for determining the convex hull of a finite planar set
• An efficient algorithm for determining the convex hull of a finite planar set
• Constructing the convex hull of a set of points in the plane
• Convex hull of a finite set of points in two dimensions
• Measuring Concavity on a Rectangular Mosaic
• On the identification of the convex hull of a finite set of points in the plane
• Sur L'enveloppe convexe des nuages de points aleatoires dans Rⁿ. I
• The design and analysis of a new hybrid sorting algorithm
• Two remarks on a convex hull algorithm
• Usort: An efficient hybrid of distributive partitioning sorting
• ZufÄllige konvexe Polygone in einem Ringgebiet

Cited in

(7)

• A modification of Graham's algorithm for determining the convex hull of a finite planar set
• scientific article; zbMATH DE number 1513407 (Why is no real title available?)
• A modified Graham's convex hull algorithm for finding the connected orthogonal convex hull of a finite planar point set
• Sorting in linear expected time
• An efficient and numerically correct algorithm for the 2D convex hull problem
• Convex-hull algorithms: implementation, testing, and experimentation
• A modification of Graham's algorithm for the convexification of a positive-uniform function

This page was built for publication: Some performance tests of convex hull algorithms

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