Optimal output-sensitive convex hull algorithms in two and three dimensions. (English) Zbl 0857.68111

Summary: We present simple output-sensitive algorithms that construct the convex hull of a set of \(n\) points in two or three dimensions in worst-case optimal \(O(n \log h)\) time and \(O(n)\) space, where \(h\) denotes the number of vertices of the convex hull.


68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
68W10 Parallel algorithms in computer science
Full Text: DOI


[1] T. M. Chan. Output-sensitive results on convex hulls, extreme points, and related problems.Discrete Comput. Geom., this issue, pp. 369-387. · Zbl 0857.68112
[2] T. M. Chan, J. Snoeyink, and C.-K. Yap. Output-sensitive construction of polytopes in four dimensions and clipped Voronoi diagrams in three.Proc. 6th ACM-SIAM Symp. on Discrete Algorithms, pp. 282-291, 1995. · Zbl 0848.68106
[3] D. R. Chand and S. S. Kapur. An algorithm for convex polytopes.J. Assoc. Comput. Mach., 17:78-86, 1970. · Zbl 0199.50902
[4] B. Chazelle. An optimal algorithm for intersecting three-dimensional convex polyhedra.SIAM J. Comput., 21:671-696, 1992. · Zbl 0825.68642
[5] B. Chazelle and D. P. Dobkin. Intersection of convex objects in two and three dimensions.J. Assoc. Comput. Mach., 34:1-27, 1987.
[6] B. Chazelle, H. Edelsbrunner, M. Grigni, L. Guibas, J. Hershberger, M. Sharir, and J. Snoeyink. Ray shooting in polygons using geodesic triangulations.Proc. 18th Internat. Colloq. on Automata, Languages, and Programming, pp. 661-673, Lecture Notes in Computer Science, vol. 510. Springer-Verlag, Berlin, 1991. · Zbl 0769.68119
[7] B. Chazelle and J. Matoušek. Derandomizing an output-sensitive convex hull algorithm in three dimensions.Comput. Geom. Theory Appl., 5:27-32, 1995. · Zbl 0814.68127
[8] K. L. Clarkson and P. W. Shor. Applications of random sampling in computational geometry, II.Discrete Comput. Geom., 4:387-421, 1989. · Zbl 0681.68060
[9] D. P. Dobkin and D. G. Kirkpatrick. Fast detection of polyhedral intersection.Theoret. Comput. Sci., 27:241-253, 1983. · Zbl 0553.68033
[10] D. P. Dobkin and D. G. Kirkpatrick. Determining the separation of preprocessed polyhedra: a unified approach.Proc. 17th Internat. Colloq. on Automata, Languages, and Programming, pp. 440-413, Lecture Notes in Computer Science, vol. 443. Springer-Verlag, Berlin, 1990. · Zbl 0765.68205
[11] H. Edelsbrunner.Algorithms in Combinatorial Geometry. Springer-Verlag, Berlin, 1987. · Zbl 0634.52001
[12] H. Edelsbrunner and E. P. Mücke. Simulation of simplicity: A technique to cope with degenerate cases in geometric algorithms.ACM Trans. Graphics, 9:66-104, 1990. · Zbl 0732.68099
[13] H. Edelsbrunner and W. Shi. AnO (n log2h) time algorithm for the three-dimensional convex hull problem.SIAM J. Comput., 20:259-277, 1991. · Zbl 0722.68064
[14] I. Emiris and J. Canny. An efficient approach to removing geometric degeneracies.Proc. 8th ACM Symp. on Computational Geometry, pp. 74-82, 1992.
[15] R. L. Graham. An efficient algorithm for determining the convex hull of a finite planar set.Inform. Process. Lett., 1:132-133, 1972. · Zbl 0236.68013
[16] S. Hart and M. Sharir. Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes.Combinatorica, 6:151-177, 1986. · Zbl 0636.05003
[17] J. Hershberger. Finding the upper envelope ofn line segments inO (n logn) time.Inform. Process. Lett., 33:169-174, 1989. · Zbl 0689.68058
[18] J. Hershberger and S. Suri. A pedestrian approach to ray shooting: shoot a ray, take a walk.Proc. 4th ACM-SIAM Symp. on Discrete Algorithms, pp. 54-63, 1993. · Zbl 0801.68159
[19] R. A. Jarvis. On the identification of the convex hull of a finite set of points in the plane.Inform. Process. Lett., 2:18-21, 1973. · Zbl 0256.68041
[20] D. G. Kirkpatrick and R. Seidel. The ultimate planar convex hull algorithm?SIAM J. Comput., 15: 287-299, 1986. · Zbl 0589.68035
[21] K. Mulmuley.Computational Geometry: An Introduction Through Randomized Algorithms. Prentice-Hall, Englewood Cliffs, NJ, 1994.
[22] J. O’Rourke, C.-B. Chien, T. Olson, and D. Naddor. A new linear algorithm for intersecting convex polygons.Comput. Graph. Image Process., 19:384-391, 1982. · Zbl 0533.52001
[23] J. O’Rourke,Computational Geometry in C. Cambridge University Press, Cambridge, 1994. · Zbl 0816.68124
[24] F. P. Preparata and S. J. Hong. Convex hulls of finite sets of points in two and three dimensions.Commun. ACM, 20:87-93, 1977. · Zbl 0342.68030
[25] F. P. Preparata and M. I. Shamos.Computational Geometry: An Introduction. Springer-Verlag, New York, 1985. · Zbl 0759.68037
[26] G. F. Swart. Finding the convex hull facet by facet.J. Algorithms, 6:17-48, 1985. · Zbl 0563.68041
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.