On the Hausdorff and Other Cluster Voronoi Diagrams

You are cordially invited to attend the PhD Dissertation Defense of Elena KHRAMTCOVA on Thursday, June 16th 2016 at 14h30 in room SI-003 (Informatics building)

Abstract:

The Voronoi diagram is a fundamental geometric structure that encodes proximity information. Given a set of geometric objects, called sites, their Voronoi diagram is a subdivision of the underlying space into maximal regions such that all points within one region have the same nearest site. Problems in diverse application domains (such as VLSI CAD, robotics, facility location, and others) call for various generalizations of this simple concept. While many generalized Voronoi diagrams have been well studied, many others still have unsettled questions. An example of the latter are cluster Voronoi diagrams, whose sites are sets (clusters) of objects rather than individual objects.

This dissertation studies certain cluster Voronoi diagrams from the perspective of their construction algorithms and algorithmic applications. Our main focus is the Hausdorff Voronoi diagram; we also consider the farthest-segment Voronoi diagram, as well as some special cases of the farthest-color Voronoi diagram. We establish a connection between the Hausdorff and the farthest-color diagram, and the stabbing circle problem for segments in the plane.

The results are as follows.

(1) We investigate the randomized incremental construction (RIC) for the Hausdorff Voronoi diagram. We consider separately the case of non-crossing clusters, when the combinatorial complexity of the diagram is O(n) where n is the total number of points in the given clusters. For this case, we present two construction algorithms that run in O(n log^2 n) expected time. For the general case of arbitrary clusters, we present an algorithm that requires O((m+n log n) log n) expected time and O(m + n log n) expected space, where m is a parameter reflecting the number of crossings between clusters' convex hulls.

(2) We present an O(n) time algorithm to construct the farthest-segment Voronoi diagram of n segments, after the sequence of its faces at infinity is known. This augments the well-known linear-time framework for Voronoi diagram of points in convex position, with the ability to handle disconnected Voronoi regions.

(3) The connection between cluster Voronoi diagrams (the Hausdorff and the farthest-color Voronoi diagram) and the stabbing circle problem implies a new method to solve this problem. Our method results in a near-optimal O(n log^2 n) time algorithm for a set of n parallel segments, and in an optimal O(n log n) time algorithm for a set of n segments satisfying some other special conditions. A byproduct is an O(n log n) time algorithm to compute the farthest-color Voronoi diagram related to such sets of segments.

Dissertation Committee:

• Prof. Evanthia Papadopoulou, Università della Svizzera italiana, Switzerland (Research Advisor)
• Prof. Antonio Carzaniga, Università della Svizzera italiana, Switzerland (Internal Member)
• Prof. Kai Hormann, Università della Svizzera italiana, Switzerland (Internal Member)
• Prof. Franz Aurenhammer, TU Graz, Austria (External Member)
• Prof. Stefan Lagerman, Université Libre de Bruxelles, Belgium (External Member)