The Visibility Center of a Simple Polygon

Abstract

We introduce the \emph{visibility center} of a set of points inside a polygon -- a point $c_V$ such that the maximum geodesic distance from $c_V$ 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 \emph{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.

arXiv commentFull-length version of a paper that appeared at the European Symposium of Algorithms 2021