Abstract
We present an algorithm for computing certain kinds of three-dimensional convex hulls in linear time. Using this algorithm, we show that the Voronoi diagram ofn sites in the plane can be computed in Θ(n) time when these sites form the vertices of a convex polygon in, say, counterclockwise order. This settles an open problem in computational geometry. Our techniques can also be used to obtain linear-time algorithms for computing the furthest-site Voronoi diagram and the medial axis of a convex polygon and for deleting a site from a general planar Voronoi diagram.
Article PDF
Similar content being viewed by others
References
L. P. Chew, Constrained Delaunay triangulations,Proc. 3rd Annual ACM Symposium on Computational Geometry, 1987, pp. 223–232.
L. J. Guibas and J. Stolfi, Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams,ACM Trans. Graphics 4 (1985), 74–123.
D. G. Kirkpatrick, Efficient computation of continuous skeletons,Proc. 20th IEEE Annual Symposium on Foundations of Computer Science, 1979, pp. 18–27.
D. G. Kirkpatrick, Optimal search in planar subdivisions,SIAM J. Comput. 12 (1983), 28–35.
D. T. Lee, Onk-nearest neighbor Voronoi diagrams in the plane,IEEE Trans. Comput. 31 (1982), 478–487.
D. T. Lee and A. K. Lin, Generalized Delaunay triangulations of planar graphs,Discrete Comput. Geom. 1 (1986), 201–217.
D. McCallum and D. Avis, A linear-time algorithm for finding the convex hull of a simple polygon,Inform. Process. Lett. 9 (1979), 201–206.
F. P. Preparata, The medial axis of a simple polygon, inMathematical Foundations of Computer Science 1977 (Proc. 6th Symp.), 443–450, Lecture Notes in Computer Science, Vol. 53, Springer-Verlag, Berlin, 1977.
F. P. Preparata and M. I. Shamos,Computational Geometry: An Introduction, Springer-Verlag, New York, 1985.
M. I. Shamos, Computational Geometry, Ph.D. thesis, Yale University, New Haven, CT, 1978.
C. A. Wang and L. Schubert, An optimal algorithm for constructing the Delaunay triangulation of a set of segments,Proc. 3rd Annual ACM Symposium on Computational Geometry, 1987, pp. 223–232.
Author information
Authors and Affiliations
Additional information
This research began while the first and fourth authors were visiting the Mathematical Sciences Research Institute in Berkeley, California. Work by the fourth author was supported in part by NSF Grant No. 8120790.
Rights and permissions
About this article
Cite this article
Aggarwal, A., Guibas, L.J., Saxe, J. et al. A linear-time algorithm for computing the voronoi diagram of a convex polygon. Discrete Comput Geom 4, 591–604 (1989). https://doi.org/10.1007/BF02187749
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/BF02187749