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) Convex sets in (2) dimensions (including convex curves) (52A10) Polytopes and polyhedra (52Bxx) Algorithms in computer science (68W99)

Review text

The authors test the two-dimensional convex hull algorithms of \textit{R. L. Graham} [Inf. Process. Lett. 1, 132-133 (1972; Zbl 0236.68013)], \textit{R. A. Jarvis} [Inf. Process. Lett. 2, 18-21 (1973; Zbl 0256.68041)], \textit{W. F. Eddy}[ACM Trans. math. Software 3, 398-403 (1977; Zbl 0374.68036)] and \textit{S. G. Akl} and \textit{G. T. Toussaint} [Inf. Process. Lett. 7, 219-222 (1978; Zbl 0392.52003)], by comparing Fortran implementations of them on four different planar point distributions. Several modifications of both the Graham and Jarvis algorithms are considered. The running times obtained by these experiments indicate that the Graham algorithm is the most convenient on point distributions where most of the points are on or near the boundary of the hull, while the Eddy and Akl-Toussaint algorithms are the bests for uniform distributions of points in the plane. The authors suggest that the design of significantly better convex hull algorithms requires the development of a faster sort algorithm.

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

• A fast convex hull algorithm
• A Lower Bound to Finding Convex Hulls
• A New Convex Hull Algorithm for Planar Sets
• 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
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• 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

(8)

• Sorting in linear expected time
• Convex-hull algorithms: implementation, testing, and experimentation
• A modification of Graham's algorithm for the convexification of a positive-uniform function
• A modified Graham's convex hull algorithm for finding the connected orthogonal convex hull of a finite planar point set
• 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 manual comparison of convex hull algorithms (multimedia exposition)
• An efficient and numerically correct algorithm for the 2D convex hull problem

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)