2021/08/16 by Lubiw, Anna, Naredla, Anurag Murty · 1 citation
#Computational Geometry (cs.CG) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2108.07366
We introduce the visibility center of a set of points inside a polygon -- a point cV such that the maximum geodesic distance from cV to see any point in the set is minimized. For a simple polygon of n vertices and a set of m points inside it, we give an O((n+m) log (n+m)) time algorithm to find the visibility center. We find the visibility center of all points in a simple polygon in O(n log n) time. Our algorithm reduces the visibility center problem to the problem of finding the geodesic center of a set of half-polygons inside a polygon, which is of independent interest. We give an O((n+k) log (n+k)) time algorithm for this problem, where k is the number of half-polygons.