# 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.