Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, May 12, 2015, 12:15 pm
Duration: 30 minutes
Location: CAB G51
Speaker: Luis Barba (Carleton University / Université Libre de Bruxelles)
Let $P$ be a closed simple polygon with $n$ vertices. For any two points in $P$, the geodesic distance between them is the length of the shortest path that connects them among all paths contained in $P$.
The geodesic center of $P$ is the unique point in $P$ that minimizes the largest geodesic distance to all other points of $P$. In 1989, Pollack, Sharir and Rote [Disc. & Comput. Geom. 89] showed an $O(n\log n)$-time algorithm that computes the geodesic center of $P$. Since then, a longstanding question has been whether this running time can be improved (explicitly posed by Mitchell [Handbook of Computational Geometry, 2000]). In this talk, we affirmatively answer this question and present a linear time algorithm to solve this problem.
Extending the techniques used by this algorithm, we study the following problem: Given a set $S\subset \partial P$ of $m$ sites sorted in clockwise order along $\partial P$, compute the geodesic farthest-point Voronoi diagram of $S$. Aronov et al. [Disc. & Comput. Geom. 93] showed how to compute this diagram in $O((n+m) \log (n+m))$ time. In this talk, we improve this result and show how to obtain this diagram in $O(n + m)$ time.
This is joint work with Hee-Kap Ahn, Prosenjit Bose, Jean-Lou De Carufel, Matias Korman and Eunjin Oh.
Automatic MiSe System Software Version 1.4803M | admin login