Technical report detail

Randomized incremental construction of the Hausdorff Voronoi diagram of non-crossing clusters

by Panagiotis Cheilaris, Elena Khramtcova, Evanthia Papadopoulou

The Hausdorff Voronoi diagram of a set of clusters of points in the plane is a generalization of the classic Voronoi diagram, where distance between a point $t$ and a cluster $P$ is measured as the maximum distance, or equivalently the Hausdorff distance between $t$ and $P$. The size of the diagram for non-crossing clusters is $O(n)$, where $n$ is the total number of points in all clusters. In this paper we present algorithms for efficiently computing the Hausdorff Voronoi diagram of non-crossing point clusters. Our algorithms are incremental and use linear space. If the clusters of points are inserted in a random order, then our best complexity algorithm takes expected time $O(n \log^2{n} (\log\log{n})^2)$ and worst-case space $O(n)$ to construct the diagram. We also provide a simpler-to-implement algorithm, based on a randomized hierarchical point-location data-structure (the Voronoi hierarchy) that takes expected time $O(n \log^3 n)$ and expected space $O(n)$. Previous (deterministic) algorithms in the Euclidean metric either require time $O(n \log^4 n)$ and $O(n \log^2 n)$ space, or have linear space complexity, but result in at least quadratic time-complexity bounds in the worst case. In order to achieve our bounds, we augment our data structures with the ability to efficiently handle non-standard characteristics of generalized Voronoi diagrams, such as sites of non-constant complexity, sites that are not enclosed in their Voronoi regions, and empty Voronoi regions. To the best of our knowledge these issues have not been addressed simultaneously by randomized incremental constructions for Voronoi diagrams. The Hausdorff Voronoi diagram finds direct application in VLSI Critical Area Analysis for computing the probability of fault in a VLSI layout due to random manufacturing defects.

Technical report 2012/03, December 2012

BibTex entry

@techreport{12randomized, author = {Panagiotis Cheilaris and Elena Khramtcova and Evanthia Papadopoulou}, title = {Randomized incremental construction of the Hausdorff Voronoi diagram of non-crossing clusters}, institution = {University of Lugano}, number = {2012/03}, year = 2012, month = dec }