# Mittagsseminar (in cooperation with M. Ghaffari, A. Steger and B. Sudakov)

__Mittagsseminar Talk Information__ | |

**Date and Time**: Thursday, April 19, 2018, 12:15 pm

**Duration**: 30 minutes

**Location**: CAB G51

**Speaker**: Chih-Hung Liu

## A Nearly Optimal Algorithm for the Geodesic Voronoi Diagram of Points in a Simple Polygon

The geodesic Voronoi diagram of m point sites inside a simple polygon of n vertices is a subdivision of the polygon into m cells, one to each site, such that all points in a cell share the same nearest site under the geodesic distance. The best known lower bound for the construction time is Omega( n + m log m ), and a matching upper bound is a long-standing open question. The state-of-the-art construction algorithms achieve O( (n+m) log (n+m) ) and O( n + m log m log^2 n ) time, which are optimal for m = Omega(n) and m = O( n / log^3 n ), respectively. In this paper, we give a construction algorithm with O( n + m ( log m + log^2 n ) ) time, and it is nearly optimal in the sense that if a single Voronoi vertex can be computed in O( log n ) time, then the construction time will become the optimal O( n + m log m ). In other words, we reduce the problem of constructing the diagram in the optimal time to the problem of computing a single Voronoi vertex in O( log n) time. This work will appear in the International Symposium on Computational Geometry, 2018.

Upcoming talks | All previous talks | Talks by speaker | Upcoming talks in iCal format (beta version!)

Previous talks by year: 2019 2018 2017 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M | admin login