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 -