# 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}

**Attachments**- hvdtr (311 KB)

*
*