2013/12/13 by Panagiotis Cheilaris, Cheilaris, Panagiotis, Elena Khramtcova +5
Computer Science · #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Data Management and Algorithms #Digital Image Processing Techniques #FOS: Computer and information sciences #cs.CG
paper · pdf · doi:10.48550/arxiv.1312.3904
arXiv admin note: substantial text overlap with arXiv:1306.5838
openalex publication_date 2013/12/13 · arxiv created 2016/03/05 · arxiv updated 2016/03/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 %El."non-crossing" 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(nlog2n) 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.