The Farthest Point Geodesic Voronoi Diagram of Points on the Boundary of a Simple Polygon
Given a set of sites (points) in a simple polygon, the farthest point geodesic Voronoi diagram partitions the polygon into cells, at most one cell per site, such that every point in a cell has the same farthest site with respect to the geodesic metric. We present an O((n+m)loglogn) time algorithm to compute the farthest point geodesic Voronoi diagram for m sites lying on the boundary of a simple n gon.
SoCG