The quickhull algorithm for convex hulls

TLDR

The convex hull is the smallest convex set containing a point set, yet computational geometry algorithms often assume well‑behaved inputs, which can lead to serious errors with floating‑point arithmetic, especially compared to randomized incremental algorithms for convex hull and Delaunay triangulation. The article proposes a practical convex hull algorithm that merges Quickhull with the Beneath‑Beyond algorithm and outlines a solution for computing hulls in two, three, or four dimensions. The algorithm merges Quickhull with Beneath‑Beyond, producing thick facets that encompass all exact convex hulls and a variant that works effectively in five or more dimensions. Empirical tests show the algorithm runs faster on inputs with non‑extreme points and uses less memory.

Abstract

The convex hull of a set of points is the smallest convex set that contains the points. This article presents a practical convex hull algorithm that combines the two-dimensional Quickhull algorithm with the general-dimension Beneath-Beyond Algorithm. It is similar to the randomized, incremental algorithms for convex hull and delaunay triangulation. We provide empirical evidence that the algorithm runs faster when the input contains nonextreme points and that it used less memory. computational geometry algorithms have traditionally assumed that input sets are well behaved. When an algorithm is implemented with floating-point arithmetic, this assumption can lead to serous errors. We briefly describe a solution to this problem when computing the convex hull in two, three, or four dimensions. The output is a set of “thick” facets that contain all possible exact convex hulls of the input. A variation is effective in five or more dimensions.