Skip to content

The quickhull algorithm for convex hulls

C. Bradford Barber, David Dobkin, Hannu T. Huhdanpaa

ACM Transactions on Mathematical Software · 1996 · 5,562 citationsOpen access

No retraction on record in OpenAlex.Check Crossref now

Cite this paper

Barber, C. B., Dobkin, D., & Huhdanpaa, H. T. (1996). The quickhull algorithm for convex hulls. ACM Transactions on Mathematical Software, 22(4), 469–483. https://doi.org/10.1145/235815.235821

In text: (Barber et al., 1996)

Ask a question about this research

One question, free, no account. Anchorcite finds the papers, checks each against Crossref and links every sentence of the answer to the passage it comes from.

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.

  1. Combinatorial Optimization: Algorithms and Complexity.1984
  2. Integer and Combinatorial Optimization1990
  3. Voronoi diagrams—a survey of a fundamental geometric data structure1991
  4. The Nucleolus of a Characteristic Function Game1969

Metadata from OpenAlex (CC0). Citations are generated from the published record.