The L_∞ Hausdorff Voronoi diagram revisited

We revisit the L_∞ Hausdorff Voronoi diagram of clusters of points, equivalently, the _∞ 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 _∞ 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(n ²), m ≤ M, but m = M, in the worst case. In practice m, M ≪ n², 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.