Convex-hull algorithms: implementation, testing, and experimentation

DOI10.3390/a11120195zbMath1461.68242OpenAlexW2902175566WikidataQ128853541 ScholiaQ128853541MaRDI QIDQ1712057

Ask Neve Gamby, Jyrki Katajainen

Publication date: 21 January 2019

Published in: Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

performancealgorithmrobustnessconvex hulltestingimplementationcomputational geometryexperimentationalgorithm engineeringrectilinear convex hull

Mathematics Subject Classification ID

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

Related Items (3)

On the optimal separating hyperplane for arbitrary sets: a generalization of the SVM formulation and a convex hull approach ⋮ Guaranteed deterministic approach to superhedging: a numerical experiment ⋮ Convex-hull algorithms: implementation, testing, and experimentation

Uses Software

• gmp
• Qhull
• Quicksort
• heapsort

Cites Work

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

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