The quickhull algorithm for convex hulls

ABSTRACT

The convex hull of a set of points is the smallest convex set that contains the points. This article presents a practial 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: Franz Aurenhammer, Voronoi diagrams—a survey of a fundamental geometric data structure, ACM Computing Surveys (CSUR), v.23 n.3, p.345-405, Sept. 1991 [doi>10.1145/116873.116880]
• 3: David Avis , David Bremner, How good are convex hull algorithms?, Proceedings of the eleventh annual symposium on Computational geometry, p.20-28, June 05-07, 1995, Vancouver, British Columbia, Canada [doi>10.1145/220279.220282]
• 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: Jean-Daniel Boissonnat , Monique Teillaud, On the randomized construction of the Delaunay tree, Theoretical Computer Science, v.112 n.2, p.339-354, May 10, 1993 [doi>10.1016/0304-3975(93)90024-N]
• 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: Donald R. Chand , Sham S. Kapur, An Algorithm for Convex Polytopes, Journal of the ACM (JACM), v.17 n.1, p.78-86, Jan. 1970 [doi>10.1145/321556.321564]
• 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: K. L. Clarkson , P. W. Shor, Applications of random sampling in computational geometry, II, Discrete & Computational Geometry, v.4 n.5, p.387-421, 1989 [doi>10.1007/BF02187740]
• 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: Kenneth L. Clarkson , Kurt Mehlhorn , Raimund Seidel, Four results on randomized incremental constructions, Computational Geometry: Theory and Applications, v.3 n.4, p.185-212, Sept. 1993 [doi>10.1016/0925-7721(93)90009-U]
• 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: Tamal K. Dey , Kokichi Sugihara , Chandrajit L. Bajaj, Delaunay triangulations in three dimensions with finite precision arithmetic, Computer Aided Geometric Design, v.9 n.6, p.457-470, Dec. 1992 [doi>10.1016/0167-8396(92)90044-P]
• 18: William F. Eddy, A New Convex Hull Algorithm for Planar Sets, ACM Transactions on Mathematical Software (TOMS), v.3 n.4, p.398-403, Dec. 1977 [doi>10.1145/355759.355766]
• 19: H. Edelsbrunner , N. R. Shah, Incremental topological flipping works for regular triangulations, Proceedings of the eighth annual symposium on Computational geometry, p.43-52, June 10-12, 1992, Berlin, Germany [doi>10.1145/142675.142688]
• 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: Komei Fukuda , Alain Prodon, Double Description Method Revisited, Selected papers from the 8th Franco-Japanese and 4th Franco-Chinese Conference on Combinatorics and Computer Science, p.91-111, July 03-05, 1995
• 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: Barry Joe, Construction of three-dimensional Delaunay triangulations using local transformations, Computer Aided Geometric Design, v.8 n.2, p.123-142, May 1991 [doi>10.1016/0167-8396(91)90038-D]
• 27: KALLAY, M. 1981. Convex hull algorithms in higher dimensions. Unpublished manuscript, Dept. of Mathematics, Univ. of Oklahoma, Norman, Okla.
• 28: David G Kirkpatrick , Raimund Seidel, The ultimate planar convex hull algorithm, SIAM Journal on Computing, v.15 n.1, p.287-299, Feb. 1986 [doi>10.1137/0215021]
• 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: Zhenyu Li , Victor Milenkovic, Constructing strongly convex hulls using exact or rounded arithmetic, Proceedings of the sixth annual symposium on Computational geometry, p.235-243, June 07-09, 1990, Berkley, California, United States [doi>10.1145/98524.98577]
• 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: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 35: R Seidel, Constructing higher-dimensional convex hulls at logarithmic cost per face, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.404-413, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12172]
• 36: Jonathan Richard Shewchuk, Triangle: Engineering a 2D Quality Mesh Generator and Delaunay Triangulator, Selected papers from the Workshop on Applied Computational Geormetry, Towards Geometric Engineering, p.203-222, May 27-28, 1996
• 37: Kokichi Sugihara, Topologically Consistent Algorithms Realted to Convex Polyhedra, Proceedings of the Third International Symposium on Algorithms and Computation, p.209-218, December 16-18, 1992
• 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.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Geometric algorithms, languages, and systems

General Terms:
Algorithms, Reliability

Keywords:
Delaunay triangulation, Voronoi diagram, convex hull, halfspace intersection