The furthest-site geodesic Voronoi diagram (Q1207795)

The authors give a time and space efficient algorithm for computing the furthest-site Voronoi diagram of \(k\) point sites with respect to the geodesic metric within a simple \(n\)-sided polygon. This algorithm consists of two steps. First the restriction of the Voronoi diagram to the boundary of the polygon and then the extension of the diagram to the interior of the polygon is computed. The first step is much more involved. The authors use and refine a method developed by S. Suri.