Department of Computer Science | Institute of Theoretical Computer Science | CADMO

Prof. Emo Welzl and Prof. Bernd Gärtner

Mittagsseminar Talk Information |

**Date and Time**: Thursday, September 05, 2019, 12:15 pm

**Duration**: 30 minutes

**Location**: CAB G 11

**Speaker**: Evanthia Papadopoulou (Università della Svizzera italiana)

The Voronoi diagram is a well-known, versatile geometric partitioning structure with numerous applications in science and engineering. Abstract Voronoi diagrams offer a unifying framework to various concrete Voronoi instances in two dimensions. Instead of sites and distance measures, abstract Voronoi diagrams are defined in terms of bisecting curves that satisfy some simple combinatorial properties. They can be constructed in optimal O(n\log n) time for n given sites. In addition, for certain tree-like Voronoi diagrams, linear-time construction algorithms have been well-known to exist. Examples include the Voronoi diagram of points in convex position, updating a Voronoi diagram of point-sites after deletion of one site, constructing the farthest-point Voronoi diagram after the convex hull, and others. Surprisingly, no linear-time constructions have been available for any non-point sites (except the medial axis of a simple polygon) nor for abstract Voronoi diagrams.

In this talk I will present a relaxed Voronoi structure for trees (and forests) within a simply connected domain D, termed a Voronoi-like diagram. The involved sites are represented by a *boundary curve* that is derived from the boundary of D. The Voronoi-like region of one site (along the boundary curve) is defined in terms of only a simple *monotone* path in the arrangement of bisectors involving that site. In contrast, the boundary of a real Voronoi region is always an *envelope* in the same arrangement. This structure turns out to have nice properties and is always well defined. Using Voronoi like-diagrams we can derive simple linear-time randomized algorithms to compute tree- and forrest-like abstract Voronoi diagrams in the aforementioned cases. This implies linear-time constructions for all the corresponding concrete diagrams that fall under their umbrella.

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

Previous talks by year: 2023 2022 2021 2020 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