The $L_\infty$ Hausdorff Voronoi Diagram Revisited
Evanthia Papadopoulou, Jinhui Xu · 2011
We revisit the L∞Hausdorff Voronoi diagram of clusters of points, equivalently, the L∞Hausdorff Voronoi diagram of rectangles, and present a plane sweep algorithm for its construction that generalizes and improves upon previous results. We show that the structural complexity of the L∞Hausdorff Voronoi diagram is Θ (n+m), where n is the number of given clusters and m is the number of essential pairs of crossing clusters. The algorithm runs in O((n+M) log n) time and O(n + M) space where M is the number of potentially essential crossings; m,M are O(n2), m ≤ M, but m = M, in the worst case. In practice m,M2, as the total number of crossings in the motivating application is typically small. For non-crossing clusters, the algorithm is optimal running in O(n log n)-time and O(n)-space. The L∞Hausdorff Voronoi diagram finds applications, among others, in the geometric min-cut problem, VLSI critical area analysis for via-blocks and open faults.