A Randomized Incremental Algorithm for the Hausdorff Voronoi Diagram of Non-crossing Clusters
| Autor: | Cheilaris, Panagiotis, Khramtcova, Elena, Langerman, Stefan, Papadopoulou, Evanthia |
|---|---|
| Rok vydání: | 2013 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | In the Hausdorff Voronoi diagram of a family of \emph{clusters of points} in the plane, the distance between a point $t$ and a cluster $P$ is measured as the maximum distance between $t$ and any point in $P$, and the diagram is defined in a nearest-neighbor sense for the input clusters. In this paper we consider %El."non-crossing" \emph{non-crossing} clusters in the plane, for which the combinatorial complexity of the Hausdorff Voronoi diagram is linear in the total number of points, $n$, on the convex hulls of all clusters. We present a randomized incremental construction, based on point location, that computes this diagram in expected $O(n\log^2{n})$ time and expected $O(n)$ space. Our techniques 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. The diagram finds direct applications in VLSI computer-aided design. Comment: arXiv admin note: substantial text overlap with arXiv:1306.5838 |
| Databáze: | arXiv |
| Externí odkaz: |
|