AbstractThe problem of constructing the

geodesic Voronoi diagramfor a set of sitesSwith a set of parallel line segmentsOas 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|=nand |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. Whenm=0, the algorithm produces the original Voronoi diagram for the sitesSin O(nlogn) time and O(n) space, and when the sites inSare assigned weights, a minor modification of the algorithm can construct the weighted Voronoi diagram forSin O(nlogn) 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(nlogn) 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(nlogn) plane-sweep algorithm forL_1 andL_\infty Delaunay triangulations. Algorithmica, 6:207-221, 1991.