AbstractThe problem of constructing the geodesic Voronoi diagram for a set of sites S with a set of parallel line segments O as obstacles is addressed and an O((m+n)log(m+n)) time and O(m+n) space algorithm is presented for constructing the diagram, where |S|=n and |O|=m. The algorithm is a plane-sweep algorithm which does not use geometric transformation. It uses two plane sweeps, advancing from two opposite directions, to produce two data structures, called the shortest path maps. The two maps are then tailored to produce the desired geodesic Voronoi diagram. When m=0, the algorithm produces the original Voronoi diagram for the sites S in O(n log n) time and O(n) space, and when the sites in S are assigned weights, a minor modification of the algorithm can construct the weighted Voronoi diagram for S in O(n log n) time and O(n) space.
Categories and Subject Descriptors: I.2.3 [Artificial Intelligence]: Deduction and Theorem Proving; F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems
Additional Key Words and Phrases: geodesic Voronoi diagrams, geodesic distance, proximity, computational geometry, analysis of algorithms, plane-sweep
Selected references
- Steven Fortune. A sweepline algorithm for Voronoi diagrams. Algorithmica, 2:153-174, 1987.
- F. K. Hwang. An O(n log n) algorithm for rectilinear minimal spanning trees. Journal of the ACM, 26(2):177-182, April 1979.
- Gary M. Shute, Linda L. Deneen, and Clark D. Thomborson. An O(n log n) plane-sweep algorithm for L_1 and L_\infty Delaunay triangulations. Algorithmica, 6:207-221, 1991.