Convex-hull algorithms: implementation, testing, and experimentation

DOI10.3390/A11120195MaRDI QIDQ1712057zbMATH OpenOpenAlexWikidataFDO

Authors Ask Neve Gamby, Jyrki Katajainen

Publication date 21 January 2019

Published in Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.3390/a11120195

zbMATH Keywords

performancerobustnesstestingalgorithmcomputational geometryconvex hullexperimentationimplementationalgorithm engineeringrectilinear convex hull

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational aspects related to convexity (52B55)

Recommendations

• Some performance tests of convex hull algorithms
• The quickhull algorithm for convex hulls
• The Ultimate Planar Convex Hull Algorithm?
• An efficient and numerically correct algorithm for the 2D convex hull problem
• The implementation of an algorithm to find the convex hull of a set of three-dimensional points

Cites work

• scientific article; zbMATH DE number 4051016 (Why is no real title available?)
• scientific article; zbMATH DE number 1956216 (Why is no real title available?)
• scientific article; zbMATH DE number 2104357 (Why is no real title available?)
• scientific article; zbMATH DE number 910884 (Why is no real title available?)
• scientific article; zbMATH DE number 1424302 (Why is no real title available?)
• A New Convex Hull Algorithm for Planar Sets
• A fast convex hull algorithm
• A note on finding convex hulls via maximal vectors
• A note on linear expected time algorithms for finding convex hulls
• Adaptive precision floating-point arithmetic and fast robust geometric predicates
• An efficient algorithm for determining the convex hull of a finite planar set
• Another efficient algorithm for convex hulls in two dimensions
• Classroom examples of robustness problems in geometric computations
• Constructing the convex hull of a set of points in the plane
• Convex hull of a finite set of points in two dimensions
• Convex-hull algorithms: implementation, testing, and experimentation
• Fast linear expected-time algorithms for computing maxima and convex hulls
• Further comments on Bykat's convex hull algorithm
• Introduction to algorithms.
• Measuring Concavity on a Rectangular Mosaic
• On a Simple, Practical, Optimal, Output-Sensitive Randomized Planar Convex Hull Algorithm
• On the Average Number of Maxima in a Set of Vectors and Applications
• On the definition and computation of rectilinear convex hulls
• On the identification of the convex hull of a finite set of points in the plane
• Optimal output-sensitive convex hull algorithms in two and three dimensions
• Quicker than Quickhull
• Randomized quickhull
• Simple floating-point filters for the two-dimensional orientation problem
• Some performance tests of convex hull algorithms
• Space-efficient planar convex hull algorithms
• Stable minimum space partitioning in linear time
• The Ultimate Planar Convex Hull Algorithm?
• The quickhull algorithm for convex hulls

Cited in

(7)

• Applications of a semi-dynamic convex hull algorithm
• Convex-hull algorithms: implementation, testing, and experimentation
• The implementation of an algorithm to find the convex hull of a set of three-dimensional points
• Guaranteed deterministic approach to superhedging: a numerical experiment
• On the optimal separating hyperplane for arbitrary sets: a generalization of the SVM formulation and a convex hull approach
• scientific article; zbMATH DE number 1513407 (Why is no real title available?)
• Experience report: growing and shrinking polygons for random testing of computational geometry algorithms

Describes a project that uses

Uses Software

• gmp
• Qhull
• Quicksort
• heapsort

This page was built for publication: Convex-hull algorithms: implementation, testing, and experimentation

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