Title: A New Approach for the Geodesic Voronoi Diagram of Points in a 
       Simple Polygon and Other Restricted Polygonal Domains

Evanthia Papadopoulou
IBM TJ Watson Research Center
Post Office Box 218
Yorktown Heights, New York 10598  
evanthia@watson.ibm.com

and

D. T. Lee*
Department of Electrical and Computer Engineering 
Northwestern University 
Evanston, IL 60208 
dtlee@ece.nwu.edu

* Supported in part by the Leonardo Fibonacci Institute in Trento, 
  Italy, by the National Science Foundation, and the Office of Naval 
  Research under the under the Grants CCR-8901815, CCR-9309743 and 
  N00014-93-1-0272.

Abstract:

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 $L_1$ metric. 

Key Words: Geodesic Voronoi diagrams, Shortest paths, Polygon
       triangulation, Topological plane sweep, Computational geometry.

Algorithmica, (20,4) April 1998, 319-352.