Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

 Mittagsseminar Talk Information

Date and Time: Tuesday, May 12, 2015, 12:15 pm

Duration: 30 minutes

Location: OAT S15/S16/S17

Speaker: Luis Barba (Carleton University / Université Libre de Bruxelles)

Linear time algorithms for geodesic problems on simple polygons

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.

Information for students and suggested topics for student talks