A Randomized Incremental Algorithm for the Hausdorff Voronoi Diagram of Non-crossing Clusters. / Cheilaris, Panagiotis; Khramtcova, Elena; Langerman, Stefan; Papadopoulou, Evanthia.
In: Algorithmica, Vol. 76, No. 4, 01.12.2016, p. 935-960.Research output: Contribution to journal › Article › peer-review
}
TY - JOUR
T1 - A Randomized Incremental Algorithm for the Hausdorff Voronoi Diagram of Non-crossing Clusters
AU - Cheilaris, Panagiotis
AU - Khramtcova, Elena
AU - Langerman, Stefan
AU - Papadopoulou, Evanthia
PY - 2016/12/1
Y1 - 2016/12/1
N2 - In the Hausdorff Voronoi diagram of a family of 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 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(nlog 2n) 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.
AB - In the Hausdorff Voronoi diagram of a family of 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 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(nlog 2n) 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.
KW - Hausdorff distance
KW - Hierarchical data structure
KW - Point location
KW - Randomized incremental construction
KW - Voronoi diagram
UR - http://www.scopus.com/inward/record.url?scp=84955559839&partnerID=8YFLogxK
U2 - 10.1007/s00453-016-0118-y
DO - 10.1007/s00453-016-0118-y
M3 - Article
AN - SCOPUS:84955559839
VL - 76
SP - 935
EP - 960
JO - Algorithmica
JF - Algorithmica
SN - 0178-4617
IS - 4
ER -
ID: 38614471