On the hausdorff and other cluster Voronoi diagrams
148 p
Thèse de doctorat: Università della Svizzera italiana, 2016
English
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, etc.) demand 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. In this dissertation we study certain cluster Voronoi diagrams from the perspective of their construction algorithms and algorithmic applications. Our main focus is the Hausdorff Voronoi diagram; we also study the farthestsegment Voronoi diagram, as well as certain special cases of the farthestcolor Voronoi diagram. We establish a connection between cluster Voronoi diagrams and the stabbing circle problem for segments in the plane. Our results are as follows. (1) We investigate the randomized incremental construction of the Hausdorff Voronoi diagram. We consider separately the case of noncrossing clusters, when the combinatorial complexity of the diagram is O(n) where n is the total number of points in all clusters. For this case, we present two construction algorithms that require O(n log2 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 farthestsegment Voronoi diagram of n segments, after the sequence of its faces at infinity is known. This augments the wellknown lineartime framework for Voronoi diagram of points in convex position, with the ability to handle disconnected Voronoi regions. (3) We establish a connection between the cluster Voronoi diagrams (the Hausdorff and the farthestcolor Voronoi diagram) and the stabbing circle problem. This implies a new method to solve the latter problem. Our method results in a nearoptimal O(n log2 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. (4) We study the farthestcolor Voronoi diagram in special cases considered by the stabbing circle problem. We prove O(n) bound for its combinatorial complexity and present an O(nlogn) time algorithm to construct it.

Language


Classification

Computer science

License

License undefined

Identifiers


Persistent URL

https://susi.usi.ch/usi/documents/318554