Convex-hull algorithms: implementation, testing, and experimentation
Summary: From a broad perspective, we study issues related to implementation, testing, and experimentation in the context of geometric algorithms. Our focus is on the effect of quality of implementation on experimental results. More concisely, we study algorithms that compute convex hulls for a multiset of points in the plane. We introduce several improvements to the implementations of the studied algorithms: \textsc{plane-sweep}, \textsc{torch}, \textsc{quickhull}, and \textsc{throw-away}. With a new set of space-efficient implementations, the experimental results -- in the integer-arithmetic setting -- are different from those of earlier studies. From this, we conclude that utmost care is needed when doing experiments and when trying to draw solid conclusions upon them.
- 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
- A fast convex hull algorithm
- A New Convex Hull Algorithm for Planar Sets
- 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
- 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?)
- 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 quickhull algorithm for convex hulls
- The Ultimate Planar Convex Hull Algorithm?
- Applications of a semi-dynamic convex hull algorithm
- Convex-hull algorithms: implementation, testing, and experimentation
- Guaranteed deterministic approach to superhedging: a numerical experiment
- Experience report: growing and shrinking polygons for random testing of computational geometry algorithms
- The implementation of an algorithm to find the convex hull of a set of three-dimensional points
- scientific article; zbMATH DE number 1513407 (Why is no real title available?)
- On the optimal separating hyperplane for arbitrary sets: a generalization of the SVM formulation and a convex hull approach
- A manual comparison of convex hull algorithms (multimedia exposition)
- A lower bound for the quickhull convex hull algorithm that disproves the quickhull precision conjecture
- Methods for identifying all extreme points of convex hulls in spaces of dimension greater than 3 revisited
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)
