The Farthest-Point Geodesic Voronoi Diagram of Points on the Boundary of a Simple Polygon
Eunjin Oh, Luis Barba, Hee-Kap Ahn · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2016
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.