Voronoi-like diagrams - Towards linear-time algorithms for tree-like abstract Voronoi diagrams

Staff - Faculty of Informatics

Date: / -

You are cordially invited to attend the PhD Dissertation Defense of Kolja Junginger on Thursday June 25th, 2020 at 14:30.
Please note that given the updated Covid-19 restrictions, the Dissertation Defense will be held online.
You can join here

Computational Geometry is a subfield of Algorithm Design and Analysis with a focus on the design and analysis of algorithms related to discrete geometric objects. The Voronoi diagram is one of the most important structures in Computational Geometry providing proximity information, which is applicable to many different fields of science. For a given set of points in the plane - called sites - the classic Voronoi diagram subdivides the plane into regions, such that all points within one region have the same nearest site. Abstract Voronoi diagrams provide a unifying model for various concrete Voronoi diagrams for different sites (e.g., disjoint line segments, non-enclosing circles) and different metrics. In the abstract framework the diagram is not defined via the sites and the distances, but from a bisecting curve system satisfying certain properties. Updating the classic Voronoi diagram of point sites, after deletion of one site, can be done in linear time as it is well known since 1989. However, this problem has remained open since then for generalized sites other than points and for abstract Voronoi diagrams. In this dissertation we present a simple, expected linear-time algorithm to update an abstract Voronoi diagram after deletion of one site. To this aim we introduce the concept of a Voronoi-like diagram, a relaxed version of a Voronoi construct that has a structure similar to an abstract Voronoi diagram, without however being one. In our algorithm Voronoi-like diagrams serve as intermediate structures, which are considerably simpler to compute. The main contribution of this dissertation is the formalization of the concept of a Voronoi-like diagram. We prove that it is well-defined and robust under an insertion operation, thus, enabling its use in incremental constructions. Further, we show that our randomized algorithm can be used to compute the order-(k+1) subdivision within the face of an order-k abstract Voronoi region in expected time linear in the complexity of the region's boundary. Moreover, our randomized algorithm can be adapted to compute the farthest abstract Voronoi diagram in expected linear-time, after the sequence of its faces at infinity is known. Finally, we have investigated the possibility to apply Voronoi-like diagrams also to a deterministic algorithmic framework for possible use in deriving deterministic versions of the above mentioned randomized algorithms. We formulate open problems, the solution of which will make progress towards this goal.

Dissertation Committee:
- Prof. Evanthia Papadopoulou, Università della Svizzera italiana, Switzerland (Research Advisor)
- Prof. Piotr Krzysztof Didyk, Università della Svizzera italiana, Switzerland (Internal Member)
- Prof. Stefan Wolf, Università della Svizzera italiana, Switzerland (Internal Member)
- Prof. Stefan Felsner, TU Berlin, Germany (External Member)
- Prof. Rolf Klein, University of Bonn, Germany (External Member)