article

Free access

The quickhull algorithm for convex hulls

Editor: Ronald Boisvert Authors:

C. Bradford Barber,

David P. Dobkin,

Hannu HuhdanpaaAuthors Info & Claims

ACM Transactions on Mathematical Software (TOMS), Volume 22, Issue 4

Pages 469 - 483

https://doi.org/10.1145/235815.235821

Published: 01 December 1996 Publication History

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.

References

[1]

ALLEN, S. AND DUTTA, D. 1995. Determination and evaluation of support structures in layered manufacturing. J. Des. Manufactur. 5, 153-162.

[2]

AURENHAMMER, F. 1991. Voronoi diagrams--A survey of a fundamental geometric data structure. ACM Cornput. Surv. 23, 345-405.

[3]

Avis, D. AND BREMNER, D. 1995. How good are convex hull Algorithms? In Proceedings of the llth Annual ACM Symposium on Computational Geomett3,. ACM, New York, 20-28.

[4]

BARBER, C. B., DOBKIN, D. P., AND HUHDANPAA, H. 1993. The Quickhull Algorithm for convex hull. Tech. Rep. GCG53, The Geometry Center, Univ. of Minnesota, Minneapolis, Minn.

[5]

BOARDMAN, J. 1993. Automating spectral unmixing of AVIRIS data using convex geometry concepts. In the 4th JPL Airborne Geoscience Workshop (Washington, D.C.). JPL, Pasadena, Calif.

[6]

BOISSONNAT, J.-D. AND TEILLAUD, M. 1993. On the randomized construction of the Delaunay tree. Theoret. Comput. Sci. 112, 339-354.

[7]

BORDIGNON, K. A. AND DURHAM, W. C. 1995. Closed-form solutions to constrained control allocation problem. J. Guidance Contr. Dynam. 18, 5, 1000-1007.

[8]

BROWN, D. 1979. Voronoi diagrams from convex hulls. Inf. Process. Lett. 9, 223-228.

[9]

BYKAT, A. 1978. Convex hull of a finite set of points in two dimensions. Inf. Process. Lett. 7, 296 -298.

[10]

CHAND, D. AND KAPUR, S. 1970. An algorithm for convex polytopes. J. ACM 7, 1, 78-86.

[11]

CHAZELLE, B. AND MATOUSEK, J. 1992. Randomizing an output-sensitive convex hull algorithm in three dimensions. Tech. Rep. TR-361-92, Princeton Univ., Princeton, N.J.

[12]

CLARKSON, K. AND SHOR, P. 1989. Applications of random sampling in computational geometry, ii. Discr. Comput. Geom. 4, 387-421.

[13]

CLARKSON, K.L. 1992. Safe and effective determinant evaluation. In Proceedings of the 31st IEEE Symposium on Foundations of Computer Science. IEEE, New York, 387-395.

[14]

CLARKSON, K. L. 1995. A program for convex hulls. ATT, Murray Hill, N.J. Available as http://netlib.att.com/netlib/voronoi/hull.html.

[15]

CLARKSON, K. L., MEHLHORN, K., AND SEIDEL, R. 1993. Four results on randomized incremental constructions. Comput. Geom. Theory Appl. 3, 185-211. Also in Lecture Notes in Computer Science. Vol. 577, pp. 463-474.

[16]

CUCKA, P., NETANYAHU, N., AND ROSENFELD, A. 1995. Learning in navigation: Goal finding in graphs. Tech. Rep. CAR-TR-759, Center for Automation Research, Univ. of Maryland, College Park, Md.

[17]

DEY, T. K., SUGIHARA, K., AND BAJAJ, C.L. 1992. Delaunay triangulations in three dimensions with finite precision arithmetic. Comput. Aided Geom. Des. 9, 457-470.

[18]

EDDY, W. 1977. A new convex hull algorithm for planar sets. ACM Trans. Math. Softw. 3, 4, 398 -403.

[19]

EDELSBRUNNER, H. AND SHAH, N. 1992. Incremental topological flipping works for regular triangulations. In Proceedings of the Symposium on Computational Geometl),. ACM, New York, 43-52.

[20]

FORTUNE, S. 1989. Stable maintenance of point-set triangulation in two-dimensions. In the 30th Annual Symposium on the Foundations of Computer Science. IEEE, New York.

[21]

FORTUNE, S. 1993. Computational geometry. In Directions in Geometric Computing, R. Martin, Ed. Information Geometers, Winchester, U.K.

[22]

FUKUDA, K. AND PRODON, A. 1996. Double description method revisited. In Lecture Notes in Computer Science, vol. 1120. Springer-Verlag, Berlin. Available also at ftp://ifor13.ethz.ch/ pub/fukudaJcdd.

[23]

GREEN P. AND SILVERMAN, B. 1979. Constructing the convex hull of a set of points in the plane. Comput. J. 22, 262-266.

[24]

GRi)NBAUM, B. 1961. Measure of symmetry for convex sets. In Proceedings of the 7th Symposium in Pure Mathematics of the American Mathematical Society, Symposium on Convexity. AMS, Providence, R.I., 233-270.

[25]

GUIBAS, L., KNUTH, D., AND SHARIR, M. 1992. Randomized incremental construction of Delaunay and Voronoi diagrams. Algorithmica 9, 534-560.

[26]

JoE, B. 1991. Construction of three-dimensional Delaunay triangulations using local transformations. Comput. Aided Geom. Des. 8, 123-142.

[27]

KALLAY, M. 1981. Convex hull algorithms in higher dimensions. Unpublished manuscript, Dept. of Mathematics, Univ. of Oklahoma, Norman, Okla.

[28]

KIRKPATRICK, U. AND SEIDEL, R. 1986. The ultimate planar convex hull algorithm? SIAM J. Comput. 15, 287-299.

[29]

KLEE, V. 1966. Convex polytopes and linear programming. In Proceedings of the IBM Scientific Computing Symposium: Combinatorial Problems. IBM, Armonk, N.Y., 123-158.

[30]

LI, Z. AND MILENKOVIC, V. 1990. Constructing strongly convex hulls using exact or rounded arithmetic. In Proceedings of the Symposium on Computational Geometry. ACM, New York, 197-207.

[31]

MOTZKIN, T. S., RAIFFA, H., THOMPSON, G. L., AND THRALL, R.M. 1953. The double description method. In Contributions of the TheolT of Games II, H. W. Kuhn and A. W. Tucker, Eds. Annals of Mathematics, vol. 8. Princeton University Press, Princeton, N.J., 51-73.

[32]

MULMULEY, D. 1994. Computational Geometry, An Introduction through Randomized Algorithms. Prentice-Hall, Englewood Cliffs, N.J.

[33]

PORTER, D., GLAVINAS, E., DHAGAT, P., O'SULLIVAN, J. A., INDECK, R. S., A~D MULLER, M. W. 1996. Irregular grain structure in micromagnetic simulation. J. Appl. Physics 79, 8, 4694-4696.

[34]

PREPARATA, D. F. AND SHAMOS, M. 1985. Computational GeometlT. An Introduction. Springer- Verlag, Berlin.

[35]

SEIDEL, R. 1986. Constructing higher-dimensional convex hulls at logarithmic cost per face. In Proceedings of the 18th ACM Symposium on the TheolT of Computing. ACM, New York, 404-413.

[36]

SHEWCHUK, J.R. 1996. Triangle: Engineering a 2D quality mesh generator and delaunay triangulator. In the 1st Workshop on Applied Computational GeometlT. ACM, New York. Also available as http://www.cs.cmu.edu/~quake/triangle.html.

[37]

SUGIHARA, K. 1992. Topologically consistent algorithms related to convex polyhedra. In Algorithms and Computation, 3rd International Symposium (ISSAC '92). Lecture Notes in Computer Science, vol. 650. Springer-Verlag, Berlin, 209-218.

[38]

WEEKS, J. 1991. Convex hulls and isometrics of cusped hyperbolic 3-manifolds. Tech. Rep. TR GCG32, The Geometry Center, Univ. of Minnesota, Minneapolis, Minn. Aug.

[39]

ZHANG, B., GOODSON, M., AND SCHREIER, R. 1994. Invariant sets for general second-order low-pass delta-sigma modulators with dc inputs. In the IEEE International Symposium on Circuits and Systems. IEEE, New York, 1-4.

Cited By

Boudreaux EChaboyer BAsh AEdaes Hoh RFeiden G(2025)Chemically Self-consistent Modeling of the Globular Cluster NGC 2808 and its Effects on the Inferred Helium Abundance of Multiple Stellar PopulationsThe Astrophysical Journal10.3847/1538-4357/ad9740980:2(180)Online publication date: 12-Feb-2025
https://doi.org/10.3847/1538-4357/ad9740
Affholder AMazevet SSauterey BApai DFerrière R(2025) Interior Convection Regime, Host Star Luminosity, and Predicted Atmospheric CO 2 Abundance in Terrestrial Exoplanets The Astronomical Journal10.3847/1538-3881/ada384169:3(125)Online publication date: 5-Feb-2025
https://doi.org/10.3847/1538-3881/ada384
Cho YShin MMan KKim M(2025)SafeWitness: Crowdsensing-Based Geofencing Approach for Dynamic Disaster Risk DetectionFractal and Fractional10.3390/fractalfract90301569:3(156)Online publication date: 3-Mar-2025
https://doi.org/10.3390/fractalfract9030156
Show More Cited By

Index Terms

The quickhull algorithm for convex hulls
1. Computing methodologies
  1. Computer graphics
    1. Shape modeling
2. Theory of computation
  1. Randomness, geometry and discrete structures

Recommendations

Convex hulls of spheres and convex hulls of disjoint convex polytopes

Given a set @S of spheres in E^d, with d>=3 and d odd, having a constant number of m distinct radii @r"1,@r"2,...,@r"m, we show that the worst-case combinatorial complexity of the convex hull of @S is @Q(@__ __"1"=<"i"<>"j"=<"mn"in"j^@__ __^d^2^@__ __), ...
Convex hulls of spheres and convex hulls of convex polytopes lying on parallel hyperplanes
SoCG '11: Proceedings of the twenty-seventh annual symposium on Computational geometry

Given a set Σ of spheres in E^d, with d≥3 and d odd, having a fixed number of m distinct radii ρ₁,ρ₂,...,ρ_m, we show that the worst-case combinatorial complexity of the convex hull CH_d(Σ) of Σ is Θ(Σ_{{1≤i≠j≤m}}n_in_j^{⌊ d/2 ⌋}), where n_i is the number of ...
Robust algorithms for constructing strongly convex hulls in parallel

Given a set S of n points in the plane, an ε-strongly convex δ-hull of S is defined as a convex polygon P with the vertices taken from S such that no point of S lies farther than δ outside P and such that even if the vertices of P are perturbed by as ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Mathematical Software

ACM Transactions on Mathematical Software Volume 22, Issue 4

Dec. 1996

116 pages

ISSN:0098-3500

EISSN:1557-7295

DOI:10.1145/235815

Editor:
Ronald Boisvert
National Institute of Standards and Technology, Guithersburg, MD

Issue’s Table of Contents

Copyright © 1996 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 December 1996

Published in TOMS Volume 22, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3,924
Total Citations
View Citations
22,360
Total Downloads

Downloads (Last 12 months)2,471
Downloads (Last 6 weeks)282

Reflects downloads up to 03 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Boudreaux EChaboyer BAsh AEdaes Hoh RFeiden G(2025)Chemically Self-consistent Modeling of the Globular Cluster NGC 2808 and its Effects on the Inferred Helium Abundance of Multiple Stellar PopulationsThe Astrophysical Journal10.3847/1538-4357/ad9740980:2(180)Online publication date: 12-Feb-2025
https://doi.org/10.3847/1538-4357/ad9740
Affholder AMazevet SSauterey BApai DFerrière R(2025) Interior Convection Regime, Host Star Luminosity, and Predicted Atmospheric CO 2 Abundance in Terrestrial Exoplanets The Astronomical Journal10.3847/1538-3881/ada384169:3(125)Online publication date: 5-Feb-2025
https://doi.org/10.3847/1538-3881/ada384
Cho YShin MMan KKim M(2025)SafeWitness: Crowdsensing-Based Geofencing Approach for Dynamic Disaster Risk DetectionFractal and Fractional10.3390/fractalfract90301569:3(156)Online publication date: 3-Mar-2025
https://doi.org/10.3390/fractalfract9030156
Boodram OScheeres D(2025)Controlling Hamiltonian Integral Invariants of Spacecraft Phase Space DistributionsJournal of Guidance, Control, and Dynamics10.2514/1.G008470(1-17)Online publication date: 7-Feb-2025
https://doi.org/10.2514/1.G008470
Hall D(2025)Ephemeris-Based Satellite Collision Rates and ProbabilitiesJournal of Spacecraft and Rockets10.2514/1.A36227(1-18)Online publication date: 22-Jan-2025
https://doi.org/10.2514/1.A36227
Boonrath ABotta E(2025)Robustness and Safety of Net-Based Debris Capture Under Deployment and Environmental UncertaintiesJournal of Spacecraft and Rockets10.2514/1.A36217(1-17)Online publication date: 7-Feb-2025
https://doi.org/10.2514/1.A36217
Böttcher LD’Orsogna MChou T(2025)Aggregating multiple test results to improve medical decision-makingPLOS Computational Biology10.1371/journal.pcbi.101274921:1(e1012749)Online publication date: 7-Jan-2025
https://doi.org/10.1371/journal.pcbi.1012749
Yang WJi JFang G(2025)A metric and its derived protein network for evaluation of ortholog database inconsistencyBMC Bioinformatics10.1186/s12859-024-06023-x26:1Online publication date: 7-Jan-2025
https://doi.org/10.1186/s12859-024-06023-x
Rui LHuang XSong SWang CWang JCao Z(2025)Largest Triangle Sampling for Visualizing Time Series in DatabaseProceedings of the ACM on Management of Data10.1145/37096993:1(1-26)Online publication date: 11-Feb-2025
https://dl.acm.org/doi/10.1145/3709699
Ammosov YKrokhalev OEliseev LSarancha GMelnikov A(2025)Method for Calculating Spatial Resolution of Heavy Ion Beam Probing for the T-15MD TokamakPhysics of Atomic Nuclei10.1134/S106377882409003587:10(1522-1528)Online publication date: 19-Feb-2025
https://doi.org/10.1134/S1063778824090035
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Figures

Tables

Media

View Issue’s Table of Contents