The Visibility Center of a Polygon

Anna Lubiw, University of Waterloo

Date and time: 2pm (New York time), Tuesday, March 30, 2021

Place: On Zoom (details provided on the seminar mailing list)

Suppose you want to guard a polygon and you have many sensors but only one guard to check on the sensors. The guard must be positioned at a point $c$ such that when a sensor at any point $q$ sends an alarm, the guard travels from $c$ on a shortest path inside the polygon to see point $q$ and the goal is to minimize the maximum distance the guard must travel. The optimum guard position $c$ is called the visibility center of the polygon.

We give an $O(n \log n)$ time algorithm to find the visibility center of a polygon. If the query points are limited to a set of size m, we can find the visibility center in time $O((n+m) \log (n+m))$. Relationships to other “centers” and to furthest Voronoi diagrams will be discussed.

Joint work with Anurag Murty Naredla.