Generalization of Voronoi Diagrams in the Plane
- 1 February 1981
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 10 (1) , 73-87
- https://doi.org/10.1137/0210006
Abstract
In this paper we study the Voronoi diagram for a set of N line segments and circles in the Euclidean plane. The diagram is a generalization of the Voronoi diagram for a set of points in the plane and has applications in wire layout, facility location, clustering and contouring problems. We present an O(N(log N)a) algorithm for constructing the diagram. It is an improvement of a previous known result which takes O(Nc"/l) time. The algorithm described in this paper is also shown to be applicable under a more general metric if certain conditions are satisfiedKeywords
This publication has 7 references indexed in Scilit:
- Voronoui Diagrams in $L_1 (L_\infty )$ Metrics with 2-Dimensional Storage ApplicationsSIAM Journal on Computing, 1980
- An O ( n log n ) Algorithm for Rectilinear Minimal Spanning TreesJournal of the ACM, 1979
- Convex hulls of finite sets of points in two and three dimensionsCommunications of the ACM, 1977
- Closest-point problemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1975
- Analytic Delineation of Thiessen Polygons*Geographical Analysis, 1973
- AN ALTERNATIVE METHOD FOR THE CONSTRUCTION OF THIESSEN POLYGONSThe Professional Geographer, 1963
- DISTRICT NO. 10, GREAT BASINMonthly Weather Review, 1911