(1) IBM TJ Watson Research Center, Yorktown Heights, NY 10598, USA
Abstract:
We study the Hausdorff Voronoi diagram of point clusters in the plane, a generalization ofVoronoi
diagrams based on the Hausdorff distance function. We derive a tight combinatorial bound on the structural
complexity of this diagram and present a plane sweep algorithm for its construction. In particular, we show
that the size of the Hausdorff Voronoi diagram is (n + m), where n is the number of points on the convex
hulls of the given clusters, and m is the number of crucial supporting segments between pairs of crossing
clusters. The plane sweep algorithm generalizes the standard plane sweep paradigm for the construction of
Voronoi diagrams with the ability to handle disconnected Hausdorff Voronoi regions. The Hausdorff Voronoi
diagram finds direct application in the problem of computing the critical area of a VLSI layout, a measure
reflecting the sensitivity of the VLSI design to spot defects during manufacturing.