The Geodesic Farthest-Point Voronoi Diagram in a Simple Polygon

摘要: Given a set of point sites in simple polygon, the geodesic farthest-point Voronoi diagram partitions polygon into cells, at most one cell per site, such that every has same farthest site with respect to metric. We present an $$O(n\log \log n+ m\log m)$$-time algorithm compute m n-gon. This improves previously best known by Aronov et al. (Discrete Comput Geom 9(3):217–255, 1993). In case all are on boundary we can $$O((n+m) n)$$ time.