The Quickhull Algorithm for Convex Hulls

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

Research output: Contribution to journalArticle

3063 Scopus citations

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 uses 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 serious 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.

Original languageEnglish (US)
Pages (from-to)469-483
Number of pages15
JournalACM Transactions on Mathematical Software
Volume22
Issue number4
DOIs
StatePublished - Dec 1996

All Science Journal Classification (ASJC) codes

  • Software
  • Applied Mathematics

Keywords

  • Algorithms
  • Convex hull
  • Delaunay triangulation
  • Halfspace intersection
  • I.3.5 [Computer Graphics]: Computational Geometry and Object Modeling - geometric algorithms, languages, and systems
  • Reliability
  • Voronoi diagram

Fingerprint Dive into the research topics of 'The Quickhull Algorithm for Convex Hulls'. Together they form a unique fingerprint.

  • Cite this