The L ∞ Hausdorff Voronoi Diagram Revisited

We revisit the L∞ Hausdorff Voronoi diagram of clusters of points in the plane and present a simple two-pass plane sweep algorithm to construct it. This problem is motivated by applications in the semiconductor industry, in particular, critical area analysis and yield prediction in VLSI design. We show that the structural complexity of this diagram is (n+m), where n is the number of given clusters and m is a number of specially crossing clusters, called essential. Our algorithm runs in O((n+m')logn) time and O(n+m') space, where m' reflects a slight superset of essential crossings, mM, and M is the total number of crossing clusters. For non-crossing clusters (M=0) or clusters with only a small number of crossings (M O(n)) the algorithm is optimal. The latter is the case of interest in the motivating application, where Mn2. This is achieved by augmenting the wavefront data structure of the plane sweep, and a preprocessing step, based on point dominance, which is interesting in its own right.