Abstract

Since the early 1980s, many classical geometric problems have been studied in the presence of polygonal obstacles. In the presence of polygonal obstacles, the distance of two points is measured by the length of a shortest path between the two points avoiding obstacles. In this talk, I introduce my recent results including an O(n+m\log m)-time algorithm for computing the Voronoi diagram of m points in a simple n-gon. This result matches the best known lower bound of \Omega(n+m\log m). This also answers the longstanding question whether the geodesic Voronoi diagram can be computed optimally, which was explicitly posed by Aronov [Algorithmica, 1989] and Mitchell [Handbook of Computational Geometry, 2000].

Bio

Eunjin Oh is an assistant professor at POSTECH.  Before joining POSTECH, she was a postdoc at Max Planck Institute for Informatics. She received her PhD from POSTECH in 2018.  Her research focuses on designing efficient algorithms for geometric problems such as the point location problem, shortest path problem and range searching problem.