PhD Seminar • Algorithms and Complexity • The Visibility Center of a Simple Polygon

Please note: This PhD seminar will be given online.

Anurag Murty Naredla, PhD candidate
David R. Cheriton School of Computer Science

Supervisor: Professor Anna Lubiw

Two points in a polygon see each other if the line segment joining them does not exit the polygon. Based on this well-studied notion, we introduce the visibility center of a set of points inside a polygon — a point c such that the maximum geodesic distance from c 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.

Joint work with Anna Lubiw.

To join this PhD seminar on Zoom, please go to https://uwaterloo.zoom.us/j/98651937935.