Nordic Journal of Computing Bibliography

Y. H. Tsin and C.-A. Wang. Geodesic Voronoi Diagrams in the Presence of Rectilinear Barriers. Nordic Journal of Computing, 3(1):1-26, Spring 1996.

The 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


  • Nordic Journal of Computing homepage
  • Bibliography top level
  • Nordic Journal of Computing Author Index
  • Search the HBP database