2013/06/25 by Panagiotis Cheilaris, Cheilaris, Panagiotis, Elena Khramtcova +3 · 1 citation
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.1306.5838
This paper has been withdrawn by the author because the substantially updated version (improved results, major text revision) is now submitted (arXiv:1312.3904)
openalex publication_date 2013/06/25 · arxiv created 2013/12/16 · arxiv updated 2013/12/17 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28
In the Hausdorff Voronoi diagram of a set of clusters of points in the plane, the distance between a point t and a cluster P is the maximum Euclidean distance between t and a point in P. This diagram has direct applications in VLSI design. We consider so-called "non-crossing" clusters. The complexity of the Hausdorff diagram of m such clusters is linear in the total number n of points in the convex hulls of all clusters. We present randomized incremental constructions for computing efficiently the diagram, improving considerably previous results. Our best complexity algorithm runs in expected time O((n + m(log log(n))2)log2(n)) and worst-case space O(n). We also provide a more practical algorithm whose expected running time is O((n + m log(n))log2(n)) and expected space complexity is O(n). To achieve these bounds, we augment the randomized incremental paradigm for the construction of Voronoi diagrams 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.