E. Papadopoulou et Dt. Lee, A NEW APPROACH FOR THE GEODESIC VORONOI DIAGRAM OF POINTS IN A SIMPLEPOLYGON AND OTHER RESTRICTED POLYGONAL DOMAINS, Algorithmica, 21(3), 1998, pp. 319-330
We introduce a new method for computing the geodesic Voronoi diagram o
f point sites in a simple polygon and other restricted polygonal domai
ns. Our method combines a sweep of the polygonal domain with the mergi
ng step of a usual divide-and-conquer algorithm. The time complexity i
s 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 L-1 metric.