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.