Some performance tests of convex hull algorithms

DOI10.1007/BF01934510zbMATH Open0584.52002OpenAlexW1987048199MaRDI QIDQ1070524FDOQ1070524

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

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?

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)

Cites Work

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

Cited In (7)

• Title not available (Why is that?)
• 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
• 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)