Higher-Order Voronoi Diagrams of Polygonal Objects

You are cordially invited to attend the PhD Dissertation Defense of Maksym ZAVERSHYNSKYI on Monday, November 24th 2014 at 13h30 in room SI-003 (Informatics building)

Abstract:
Higher-order Voronoi diagrams are fundamental geometric structures which encode the k-nearest neighbor information. Thus, they aid in computations that require proximity information beyond the nearest neighbor. They are related to various favorite structures in computational geometry and are a fascinating combinatorial problem to study.

While higher-order Voronoi diagrams of points have been studied a lot, they have not been considered for other types of sites. Points lack dimensionality which makes them unable to represent various real-life instances. Points are the simplest kind of geometric object and therefore higher-order Voronoi diagrams of points can be considered as the corner case of all higher-order Voronoi diagrams.

The goal of this dissertation is to move away from the corner and bring the higher-order Voronoi diagram to more general geometric instances. We focus on certain polygonal objects as they provide flexibility and are able to represent real-life instances. Before this dissertation, higher-order Voronoi diagrams of polygonal objects had been studied only for the nearest neighbor and farthest Voronoi diagrams. In this dissertation we investigate structural and combinatorial properties and discover that the dimensionality of geometric objects manifests itself in numerous ways which do not exist in the case of points. We prove that the structural complexity of the order-k Voronoi diagram of non-crossing line segments is O(k(n−k)), as in the case of points. We study disjoint line segments, intersecting line segments, line segments forming a planar straight-line graph and extend the results to the Lp metric, 1≤p≤∞. We also establish the connection between two mathematical abstractions: abstract Voronoi diagrams and the Clarkson-Shor framework.

We design several construction algorithms that cover the case of non-point sites. While computational geometry provides several approaches to study the structural complexity that give tight realizable bounds, developing an effective construction algorithm is still a challenging problem even for points. Most of the construction algorithms are designed to work with points as they utilize their simplicity and relations with data-structures that work specifically for points. We extend the iterative and the sweepline approaches that are quite efficient in constructing all order-i Voronoi diagrams, for i≤k and we also give three randomized construction algorithms for abstract higher-order Voronoi diagrams that deal specifically with the construction of the order-k Voronoi diagrams.

Dissertation Committee:

• Prof. Evanthia Papadopoulou, Università della Svizzera italiana, Switzerland (Research Advisor)
• Prof. Michael Bronstein, Università della Svizzera italiana, Switzerland (Internal Member)
• Prof. Kai Hormann, Università della Svizzera italiana, Switzerland (Internal Member)
• Prof. Rolf Klein, University of Bonn, Germany (External Member)
• Prof. Vera Sacristan, Universitat Politècnica de Catalunya, Spain (External Member)