DOI: 10.1145/235815.235821. The quickhull algorithm for convex hulls

The quickhull algorithm for convex hulls

10.1145/235815.235821

Crossref journal-article

Association for Computing Machinery (ACM)

ACM Transactions on Mathematical Software (320)

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.

Bibliography

Barber, C. B., Dobkin, D. P., & Huhdanpaa, H. (1996). The quickhull algorithm for convex hulls. ACM Transactions on Mathematical Software, 22(4), 469â483.

Authors 3

C. Bradford Barber (first)
David P. Dobkin (additional)
Hannu Huhdanpaa (additional)

References 36 Referenced 3,991

{'key': 'e_1_2_1_1_1', 'first-page': '153', 'article-title': 'Determination and evaluation of support structures in layered manufacturing', 'volume': '5', 'author': 'ALLEN S.', 'year': '1995', 'journal-title': 'J. Des. Manufactur.'} / J. Des. Manufactur. / Determination and evaluation of support structures in layered manufacturing by ALLEN S. (1995)
10.1145/116873.116880
{'key': 'e_1_2_1_3_1', 'first-page': '20', 'volume-title': 'Proceedings of the llth Annual ACM Symposium on Computational Geomett3,. ACM', 'author': 'BREMNER D.', 'year': '1995'} / Proceedings of the llth Annual ACM Symposium on Computational Geomett3,. ACM by BREMNER D. (1995)
{'volume-title': 'the 4th JPL Airborne Geoscience Workshop (Washington, D.C.). JPL, Pasadena, Calif.', 'year': '1993', 'author': 'BOARDMAN J.', 'key': 'e_1_2_1_5_1'} / the 4th JPL Airborne Geoscience Workshop (Washington, D.C.). JPL, Pasadena, Calif. by BOARDMAN J. (1993)
10.1016/0304-3975(93)90024-N
10.2514/3.21497 / J. Guidance Contr. Dynam. / Closed-form solutions to constrained control allocation problem by BORDIGNON K. A. (1995)
10.1016/0020-0190(79)90074-7 / Inf. Process. Lett. / Voronoi diagrams from convex hulls by BROWN D. (1979)
10.1016/0020-0190(78)90021-2 / Inf. Process. Lett. / Convex hull of a finite set of points in two dimensions by BYKAT A. (1978)
10.1145/321556.321564
{'key': 'e_1_2_1_11_1', 'article-title': 'Randomizing an output-sensitive convex hull algorithm in three dimensions', 'author': 'CHAZELLE B.', 'year': '1992', 'journal-title': 'Tech. Rep. TR-361-92, Princeton Univ., Princeton, N.J.'} / Tech. Rep. TR-361-92, Princeton Univ., Princeton, N.J. / Randomizing an output-sensitive convex hull algorithm in three dimensions by CHAZELLE B. (1992)
10.1007/BF02187740
{'key': 'e_1_2_1_13_1', 'first-page': '387', 'volume-title': 'Proceedings of the 31st IEEE Symposium on Foundations of Computer Science. IEEE', 'author': 'CLARKSON K.L.', 'year': '1992'} / Proceedings of the 31st IEEE Symposium on Foundations of Computer Science. IEEE by CLARKSON K.L. (1992)
CLARKSON K. L. 1995. A program for convex hulls. ATT Murray Hill N.J. Available as http://netlib.att.com/netlib/voronoi/hull.html. CLARKSON K. L. 1995. A program for convex hulls. ATT Murray Hill N.J. Available as http://netlib.att.com/netlib/voronoi/hull.html.
10.1016/0925-7721(93)90009-U
10.1016/0167-8396(92)90044-P
10.1145/355759.355766
{'key': 'e_1_2_1_19_1', 'first-page': '43', 'volume-title': 'Proceedings of the Symposium on Computational Geometl),. ACM', 'author': 'EDELSBRUNNER H.', 'year': '1992'} / Proceedings of the Symposium on Computational Geometl),. ACM by EDELSBRUNNER H. (1992)
{'volume-title': 'the 30th Annual Symposium on the Foundations of Computer Science. IEEE', 'year': '1989', 'author': 'FORTUNE S.', 'key': 'e_1_2_1_20_1'} / the 30th Annual Symposium on the Foundations of Computer Science. IEEE by FORTUNE S. (1989)
{'volume-title': 'Directions in Geometric Computing', 'author': 'FORTUNE S.', 'key': 'e_1_2_1_21_1'} / Directions in Geometric Computing by FORTUNE S.
{'volume-title': 'Double description method revisited', 'series-title': 'Lecture Notes in Computer Science', 'author': 'FUKUDA K.', 'key': 'e_1_2_1_22_1'} / Double description method revisited / Lecture Notes in Computer Science by FUKUDA K.
10.1093/comjnl/22.3.262 / Comput. J. / Constructing the convex hull of a set of points in the plane by GREEN P. (1979)
{'volume-title': 'Proceedings of the 7th Symposium in Pure Mathematics of the American Mathematical Society, Symposium on Convexity. AMS, Providence, R.I., 233-270', 'year': '1961', 'author': 'GR BAUM', 'key': 'e_1_2_1_24_1'} / Proceedings of the 7th Symposium in Pure Mathematics of the American Mathematical Society, Symposium on Convexity. AMS, Providence, R.I., 233-270 by GR BAUM (1961)
{'key': 'e_1_2_1_25_1', 'first-page': '534', 'article-title': 'Randomized incremental construction of Delaunay and Voronoi diagrams', 'volume': '9', 'author': 'GUIBAS L.', 'year': '1992', 'journal-title': 'Algorithmica'} / Algorithmica / Randomized incremental construction of Delaunay and Voronoi diagrams by GUIBAS L. (1992)
10.1016/0167-8396(91)90038-D
{'volume-title': 'Dept. of Mathematics, Univ. of Oklahoma', 'author': 'KALLAY M.', 'key': 'e_1_2_1_27_1'} / Dept. of Mathematics, Univ. of Oklahoma by KALLAY M.
10.1137/0215021
{'volume-title': 'Proceedings of the IBM Scientific Computing Symposium: Combinatorial Problems. IBM, Armonk, N.Y., 123-158', 'year': '1966', 'author': 'KLEE V.', 'key': 'e_1_2_1_29_1'} / Proceedings of the IBM Scientific Computing Symposium: Combinatorial Problems. IBM, Armonk, N.Y., 123-158 by KLEE V. (1966)
{'key': 'e_1_2_1_30_1', 'first-page': '197', 'volume-title': 'Proceedings of the Symposium on Computational Geometry. ACM', 'author': 'LI Z.', 'year': '1990'} / Proceedings of the Symposium on Computational Geometry. ACM by LI Z. (1990)
{'key': 'e_1_2_1_31_1', 'first-page': '51', 'volume-title': 'Eds. Annals of Mathematics', 'volume': '8', 'author': 'MOTZKIN T. S.', 'year': '1953'} / Eds. Annals of Mathematics by MOTZKIN T. S. (1953)
{'volume-title': 'An Introduction through Randomized Algorithms', 'author': 'MULMULEY D.', 'key': 'e_1_2_1_32_1'} / An Introduction through Randomized Algorithms by MULMULEY D.
10.1063/1.361708 / J. Appl. Physics / Irregular grain structure in micromagnetic simulation by PORTER D. (1996)
{'volume-title': 'Computational GeometlT. An Introduction', 'author': 'PREPARATA D. F.', 'key': 'e_1_2_1_34_1'} / Computational GeometlT. An Introduction by PREPARATA D. F.
{'key': 'e_1_2_1_35_1', 'first-page': '404', 'volume-title': 'Proceedings of the 18th ACM Symposium on the TheolT of Computing. ACM', 'author': 'SEIDEL R.', 'year': '1986'} / Proceedings of the 18th ACM Symposium on the TheolT of Computing. ACM by SEIDEL R. (1986)
{'volume-title': 'the 1st Workshop on Applied Computational GeometlT. ACM', 'year': '1996', 'author': 'SHEWCHUK J.R.', 'key': 'e_1_2_1_36_1'} / the 1st Workshop on Applied Computational GeometlT. ACM by SHEWCHUK J.R. (1996)
{'key': 'e_1_2_1_37_1', 'first-page': '209', 'volume-title': "3rd International Symposium (ISSAC '92)", 'volume': '650', 'author': 'SUGIHARA K.', 'year': '1992'} / 3rd International Symposium (ISSAC '92) by SUGIHARA K. (1992)
{'key': 'e_1_2_1_39_1', 'first-page': '1', 'volume-title': 'the IEEE International Symposium on Circuits and Systems. IEEE', 'author': 'ZHANG B.', 'year': '1994'} / the IEEE International Symposium on Circuits and Systems. IEEE by ZHANG B. (1994)

Dates

Type	When
Created	23 years ago (July 27, 2002, 7:29 a.m.)
Deposited	2 months ago (June 18, 2025, 4:01 p.m.)
Indexed	6 hours, 56 minutes ago (Aug. 21, 2025, 2:29 p.m.)
Issued	28 years, 8 months ago (Dec. 1, 1996)
Published	28 years, 8 months ago (Dec. 1, 1996)
Published Online	28 years, 8 months ago (Dec. 1, 1996)
Published Print	28 years, 8 months ago (Dec. 1, 1996)

Funders 0

None

BibTeX

@article{Barber_1996, title={The quickhull algorithm for convex hulls}, volume={22}, ISSN={1557-7295}, url={http://dx.doi.org/10.1145/235815.235821}, DOI={10.1145/235815.235821}, number={4}, journal={ACM Transactions on Mathematical Software}, publisher={Association for Computing Machinery (ACM)}, author={Barber, C. Bradford and Dobkin, David P. and Huhdanpaa, Hannu}, year={1996}, month=dec, pages={469–483} }

JSON

{
  "indexed": {
    "date-parts": [
      [
        2025,
        8,
        21
      ]
    ],
    "date-time": "2025-08-21T18:29:45Z",
    "timestamp": 1755800985548,
    "version": "3.41.0"
  },
  "reference-count": 36,
  "publisher": "Association for Computing Machinery (ACM)",
  "issue": "4",
  "license": [
    {
      "start": {
        "date-parts": [
          [
            1996,
            12,
            1
          ]
        ],
        "date-time": "1996-12-01T00:00:00Z",
        "timestamp": 849398400000
      },
      "content-version": "vor",
      "delay-in-days": 0,
      "URL": "https://www.acm.org/publications/policies/copyright_policy#Background"
    }
  ],
  "content-domain": {
    "domain": [
      "dl.acm.org"
    ],
    "crossmark-restriction": true
  },
  "published-print": {
    "date-parts": [
      [
        1996,
        12
      ]
    ]
  },
  "abstract": "<jats:p>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 \u201cthick\u201d facets that contain all possible exact convex hulls of the input. A variation is effective in five or more dimensions.</jats:p>",
  "DOI": "10.1145/235815.235821",
  "type": "journal-article",
  "created": {
    "date-parts": [
      [
        2002,
        7,
        27
      ]
    ],
    "date-time": "2002-07-27T11:29:03Z",
    "timestamp": 1027769343000
  },
  "page": "469-483",
  "update-policy": "https://doi.org/10.1145/crossmark-policy",
  "source": "Crossref",
  "is-referenced-by-count": 3991,
  "title": "The quickhull algorithm for convex hulls",
  "prefix": "10.1145",
  "volume": "22",
  "author": [
    {
      "given": "C. Bradford",
      "family": "Barber",
      "sequence": "first",
      "affiliation": [
        {
          "name": "Univ. of Minnesota, Minneapolis"
        }
      ]
    },
    {
      "given": "David P.",
      "family": "Dobkin",
      "sequence": "additional",
      "affiliation": [
        {
          "name": "Princeton Univ., Princeton, NJ"
        }
      ]
    },
    {
      "given": "Hannu",
      "family": "Huhdanpaa",
      "sequence": "additional",
      "affiliation": [
        {
          "name": "Configured Energy Systems, Inc., Plymouth, MN"
        }
      ]
    }
  ],
  "member": "320",
  "published-online": {
    "date-parts": [
      [
        1996,
        12
      ]
    ]
  },
  "reference": [
    {
      "key": "e_1_2_1_1_1",
      "first-page": "153",
      "article-title": "Determination and evaluation of support structures in layered manufacturing",
      "volume": "5",
      "author": "ALLEN S.",
      "year": "1995",
      "journal-title": "J. Des. Manufactur."
    },
    {
      "key": "e_1_2_1_2_1",
      "doi-asserted-by": "publisher",
      "DOI": "10.1145/116873.116880"
    },
    {
      "key": "e_1_2_1_3_1",
      "first-page": "20",
      "volume-title": "Proceedings of the llth Annual ACM Symposium on Computational Geomett3,. ACM",
      "author": "BREMNER D.",
      "year": "1995"
    },
    {
      "volume-title": "the 4th JPL Airborne Geoscience Workshop (Washington, D.C.). JPL, Pasadena, Calif.",
      "year": "1993",
      "author": "BOARDMAN J.",
      "key": "e_1_2_1_5_1"
    },
    {
      "key": "e_1_2_1_6_1",
      "doi-asserted-by": "publisher",
      "DOI": "10.1016/0304-3975(93)90024-N"
    },
    {
      "issue": "5",
      "key": "e_1_2_1_7_1",
      "doi-asserted-by": "crossref",
      "first-page": "1000",
      "DOI": "10.2514/3.21497",
      "article-title": "Closed-form solutions to constrained control allocation problem",
      "volume": "18",
      "author": "BORDIGNON K. A.",
      "year": "1995",
      "journal-title": "J. Guidance Contr. Dynam."
    },
    {
      "key": "e_1_2_1_8_1",
      "doi-asserted-by": "crossref",
      "first-page": "223",
      "DOI": "10.1016/0020-0190(79)90074-7",
      "article-title": "Voronoi diagrams from convex hulls",
      "volume": "9",
      "author": "BROWN D.",
      "year": "1979",
      "journal-title": "Inf. Process. Lett."
    },
    {
      "key": "e_1_2_1_9_1",
      "doi-asserted-by": "crossref",
      "first-page": "296",
      "DOI": "10.1016/0020-0190(78)90021-2",
      "article-title": "Convex hull of a finite set of points in two dimensions",
      "volume": "7",
      "author": "BYKAT A.",
      "year": "1978",
      "journal-title": "Inf. Process. Lett."
    },
    {
      "key": "e_1_2_1_10_1",
      "doi-asserted-by": "publisher",
      "DOI": "10.1145/321556.321564"
    },
    {
      "key": "e_1_2_1_11_1",
      "article-title": "Randomizing an output-sensitive convex hull algorithm in three dimensions",
      "author": "CHAZELLE B.",
      "year": "1992",
      "journal-title": "Tech. Rep. TR-361-92, Princeton Univ., Princeton, N.J."
    },
    {
      "key": "e_1_2_1_12_1",
      "doi-asserted-by": "publisher",
      "DOI": "10.1007/BF02187740"
    },
    {
      "key": "e_1_2_1_13_1",
      "first-page": "387",
      "volume-title": "Proceedings of the 31st IEEE Symposium on Foundations of Computer Science. IEEE",
      "author": "CLARKSON K.L.",
      "year": "1992"
    },
    {
      "key": "e_1_2_1_14_1",
      "unstructured": "CLARKSON K. L. 1995. A program for convex hulls. ATT Murray Hill N.J. Available as http://netlib.att.com/netlib/voronoi/hull.html.  CLARKSON K. L. 1995. A program for convex hulls. ATT Murray Hill N.J. Available as http://netlib.att.com/netlib/voronoi/hull.html."
    },
    {
      "key": "e_1_2_1_15_1",
      "doi-asserted-by": "publisher",
      "DOI": "10.1016/0925-7721(93)90009-U"
    },
    {
      "key": "e_1_2_1_17_1",
      "doi-asserted-by": "publisher",
      "DOI": "10.1016/0167-8396(92)90044-P"
    },
    {
      "key": "e_1_2_1_18_1",
      "doi-asserted-by": "publisher",
      "DOI": "10.1145/355759.355766"
    },
    {
      "key": "e_1_2_1_19_1",
      "first-page": "43",
      "volume-title": "Proceedings of the Symposium on Computational Geometl),. ACM",
      "author": "EDELSBRUNNER H.",
      "year": "1992"
    },
    {
      "volume-title": "the 30th Annual Symposium on the Foundations of Computer Science. IEEE",
      "year": "1989",
      "author": "FORTUNE S.",
      "key": "e_1_2_1_20_1"
    },
    {
      "volume-title": "Directions in Geometric Computing",
      "author": "FORTUNE S.",
      "key": "e_1_2_1_21_1"
    },
    {
      "volume-title": "Double description method revisited",
      "series-title": "Lecture Notes in Computer Science",
      "author": "FUKUDA K.",
      "key": "e_1_2_1_22_1"
    },
    {
      "key": "e_1_2_1_23_1",
      "doi-asserted-by": "crossref",
      "first-page": "262",
      "DOI": "10.1093/comjnl/22.3.262",
      "article-title": "Constructing the convex hull of a set of points in the plane",
      "volume": "22",
      "author": "GREEN P.",
      "year": "1979",
      "journal-title": "Comput. J."
    },
    {
      "volume-title": "Proceedings of the 7th Symposium in Pure Mathematics of the American Mathematical Society, Symposium on Convexity. AMS, Providence, R.I., 233-270",
      "year": "1961",
      "author": "GR BAUM",
      "key": "e_1_2_1_24_1"
    },
    {
      "key": "e_1_2_1_25_1",
      "first-page": "534",
      "article-title": "Randomized incremental construction of Delaunay and Voronoi diagrams",
      "volume": "9",
      "author": "GUIBAS L.",
      "year": "1992",
      "journal-title": "Algorithmica"
    },
    {
      "key": "e_1_2_1_26_1",
      "doi-asserted-by": "publisher",
      "DOI": "10.1016/0167-8396(91)90038-D"
    },
    {
      "volume-title": "Dept. of Mathematics, Univ. of Oklahoma",
      "author": "KALLAY M.",
      "key": "e_1_2_1_27_1"
    },
    {
      "key": "e_1_2_1_28_1",
      "doi-asserted-by": "publisher",
      "DOI": "10.1137/0215021"
    },
    {
      "volume-title": "Proceedings of the IBM Scientific Computing Symposium: Combinatorial Problems. IBM, Armonk, N.Y., 123-158",
      "year": "1966",
      "author": "KLEE V.",
      "key": "e_1_2_1_29_1"
    },
    {
      "key": "e_1_2_1_30_1",
      "first-page": "197",
      "volume-title": "Proceedings of the Symposium on Computational Geometry. ACM",
      "author": "LI Z.",
      "year": "1990"
    },
    {
      "key": "e_1_2_1_31_1",
      "first-page": "51",
      "volume-title": "Eds. Annals of Mathematics",
      "volume": "8",
      "author": "MOTZKIN T. S.",
      "year": "1953"
    },
    {
      "volume-title": "An Introduction through Randomized Algorithms",
      "author": "MULMULEY D.",
      "key": "e_1_2_1_32_1"
    },
    {
      "issue": "8",
      "key": "e_1_2_1_33_1",
      "doi-asserted-by": "crossref",
      "first-page": "4694",
      "DOI": "10.1063/1.361708",
      "article-title": "Irregular grain structure in micromagnetic simulation",
      "volume": "79",
      "author": "PORTER D.",
      "year": "1996",
      "journal-title": "J. Appl. Physics"
    },
    {
      "volume-title": "Computational GeometlT. An Introduction",
      "author": "PREPARATA D. F.",
      "key": "e_1_2_1_34_1"
    },
    {
      "key": "e_1_2_1_35_1",
      "first-page": "404",
      "volume-title": "Proceedings of the 18th ACM Symposium on the TheolT of Computing. ACM",
      "author": "SEIDEL R.",
      "year": "1986"
    },
    {
      "volume-title": "the 1st Workshop on Applied Computational GeometlT. ACM",
      "year": "1996",
      "author": "SHEWCHUK J.R.",
      "key": "e_1_2_1_36_1"
    },
    {
      "key": "e_1_2_1_37_1",
      "first-page": "209",
      "volume-title": "3rd International Symposium (ISSAC '92)",
      "volume": "650",
      "author": "SUGIHARA K.",
      "year": "1992"
    },
    {
      "key": "e_1_2_1_39_1",
      "first-page": "1",
      "volume-title": "the IEEE International Symposium on Circuits and Systems. IEEE",
      "author": "ZHANG B.",
      "year": "1994"
    }
  ],
  "container-title": "ACM Transactions on Mathematical Software",
  "original-title": [],
  "language": "en",
  "link": [
    {
      "URL": "https://dl.acm.org/doi/10.1145/235815.235821",
      "content-type": "unspecified",
      "content-version": "vor",
      "intended-application": "text-mining"
    },
    {
      "URL": "https://dl.acm.org/doi/pdf/10.1145/235815.235821",
      "content-type": "unspecified",
      "content-version": "vor",
      "intended-application": "similarity-checking"
    }
  ],
  "deposited": {
    "date-parts": [
      [
        2025,
        6,
        18
      ]
    ],
    "date-time": "2025-06-18T20:01:16Z",
    "timestamp": 1750276876000
  },
  "score": 1,
  "resource": {
    "primary": {
      "URL": "https://dl.acm.org/doi/10.1145/235815.235821"
    }
  },
  "subtitle": [],
  "short-title": [],
  "issued": {
    "date-parts": [
      [
        1996,
        12
      ]
    ]
  },
  "references-count": 36,
  "journal-issue": {
    "issue": "4",
    "published-print": {
      "date-parts": [
        [
          1996,
          12
        ]
      ]
    }
  },
  "alternative-id": [
    "10.1145/235815.235821"
  ],
  "URL": "http://dx.doi.org/10.1145/235815.235821",
  "relation": {},
  "ISSN": [
    "0098-3500",
    "1557-7295"
  ],
  "subject": [],
  "container-title-short": "ACM Trans. Math. Softw.",
  "published": {
    "date-parts": [
      [
        1996,
        12
      ]
    ]
  },
  "assertion": [
    {
      "value": "1996-12-01",
      "order": 2,
      "name": "published",
      "label": "Published",
      "group": {
        "name": "publication_history",
        "label": "Publication History"
      }
    }
  ]
}