- Title: Three Decades of Research on the Two-Center Problem

- Place: Via Zoom due to COVID-19 ( Link: https://kaist.zoom.us/j/91214104787?pwd=dzNiYWd0VDh6NXQ3T3c0ZkhWSjVDUT09 )

- Language: English

Here is the speaker's short biography and the talk's abstract:

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.

Abstract
Given a set of points in the Euclidean plane, the two-center problem asks to find two congruent disks of minimum radius whose union contains the input point set. The two-center problem is one of the classical problems in computational geometry, which has a rich history: Since the first algorithm was presented in 1991, it has been studied for a long time and has led to multiple previous works. Whether there exists an optimal ＄O(n ＼log n)＄-time algorithm is a long-standing open problem. Very recently, we close this long-standing open problem by cleverly combining various ideas in the previous work with new observations. In this talk, I will introduce several interesting ideas in the previous work and show how we obtain an optimal algorithm for the two-center problem.

If you want to get more information about the colloquium, please refer to colloquium page: https://cs.kaist.ac.kr/colloquium/