Robert F. Gordon, Edward A. MacNair, et al.
WSC 1985
We introduce a new method for computing the geodesic Voronoi diagram of point sites in a simple polygon and other restricted polygonal domains. Our method combines a sweep of the polygonal domain with the merging step of a usual divide-and-conquer algorithm. The time complexity is O((n+k) log(n+K)) where n is the number of vertices and k is the number of points, improving upon previously known bounds. Space is O(n+K). Other polygonal domains where our method is applicable include (among others) a polygonal domain of parallel disjoint line segments and a polygonal domain of rectangles in the L1 metric. © 1998 Springer-Verlag New York Inc.
Robert F. Gordon, Edward A. MacNair, et al.
WSC 1985
Imran Nasim, Melanie Weber
SCML 2024
Sankar Basu
Journal of the Franklin Institute
Igor Devetak, Andreas Winter
ISIT 2003