Abstract
We introduce a geometric transformation that allows Voronoi diagrams to be computed using a sweepline technique. The transformation is used to obtain simple algorithms for computing the Voronoi diagram of point sites, of line segment sites, and of weighted point sites. All algorithms haveO(n logn) worst-case running time and useO(n) space.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
F. Aurenhammer and H. Edelsbrunner, An optimal algorithm for constructing the weighted Voronoi diagram in the plane,Pattern Recognition,17 (1984), 251–257.
J. L. Bentley, B. W. Weide, and A. C. Yao, Optimal expected-time algorithms for closest-point problems,ACM Trans. Math. Software,6 (1980), 563–580.
L. P. Chew and R. L. Drysdale, Voronoi diagrams based on convex distance functions,Proceedings of the Symposium on Computational Geometry, 1985, pp. 235–244.
J. R. Driscoll, N. Sarnak, D. D. Sleator, and R. E. Tarjan, Making data structures persistent,Proceedings of the 18th Annual ACM Symposium on Theory of Computing, 1986, pp. 109–121.
H. Edelsbrunner, private communication, 1985.
H. Edelsbrunner, L. J. Guibas, and J. Stolfi, Optimal point location in a monotone subdivision, Technical Report, DEC Systems Research Center, Palo Alto, CA, 1984.
S. J. Fortune, Fast algorithms for polygon containment,Automata, Languages, and Programming, 12th Colloquium, Lecture Notes in Computer Science, Vol. 194, Springer-Verlag, New York, pp. 189–198.
P. J. Green and R. Sibson, Computing Dirichlet tesselations in the plane,Comput. J.,21 (1977) 168–173.
D. Kirkpatrick, Efficient computation of continuous skeletons,Proceedings of the 20th Annual Symposium on Foundations of Computer Science, 1979, pp. 18–27.
D. T. Lee, Medial axis transformation of a planar shape,IEEE Trans. Pattern Analysis Machine Intel.,4 (1982), 363–369.
D. T. Lee and R. L. Drysdale, Generalizations of Voronoi diagrams in the plane,Siam J. Comput.,10 (1981), 73–87.
D. T. Lee and B. J. Schacter, Two algorithms for constructing a Delauney triangulation,Internat. J. Comput. Inform. Sci.,9 (1980), 219–227.
D. Leven and M. Sharir, Planning a purely translational motion for a convex object in two-dimensional space using generalized Voronoi diagrams, Technical Report 34/85, Tel Aviv University, 1985.
D. Leven and M. Sharir, Intersection problems and applications of Voronoi diagrams, inAdvances in Robotics, Vol. I (J. Schwartz and C. K. Yap, eds), Lawrence Erlbaum, 1986.
T. Ohya, M. Iri, and K. Murota, Improvements of the incremental method for the Voronoi diagram with computational comparison of various algorithms,J. Oper. Res. Soc. Japan,27 (1984), 306–336.
F. P. Preparata, The medial axis of a simple polygon,Proceedings of the Sixth Symposium on Mathematical Foundations of Computer Science, Lecture Notes in Computer Science, Vol. 53, Springer-Verlag, New York, 1977, pp. 443–450.
F. P. Preparata and M. I. Shamos,Computational Geometry: An Introduction, Springer-Verlag, New York, 1985.
M. I. Shamos and D. Hoey, Closest-point problems,Proceedings of the 16th Annual Symposium on Foundations of Computer Science, 1975, pp. 151–162.
M. Sharir, Intersection and closest-pair problems for a set of planar discs,SIAM J. Comput.,14 (1985), 448–468.
R. Sedgewick,Algorithms, Addison Wesley, Reading, MA, 1983.
C. K. Yap, AnO(n logn) algorithm for the Voronoi diagram of a set of simple curve segments, NsYU-Courant Robotics Report No. 43 (submitted toSIAM J. Comput.).
Author information
Authors and Affiliations
Additional information
Communicated by Bernard Chazelle.
Rights and permissions
About this article
Cite this article
Fortune, S. A sweepline algorithm for Voronoi diagrams. Algorithmica 2, 153–174 (1987). https://doi.org/10.1007/BF01840357
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01840357