Title: The Hausdorff Voronoi Diagram  of Polygonal Objects: A Divide and Conquer Approach*

Evanthia Papadopoulou
IBM TJ Watson Research Center
P.O. Box 218, Yorktown Heights, NY 10598
E-mail: evanthia@watson.ibm.com

and 

D. T. Lee
Institute of Information Science
Academia Sinica
Nankang, Taipei, Taiwan 115
E-mail: dtlee@iis.sinica.edu.tw

* Supported in part by the National Science Council
  under the Grants NSC-93-2213-E-001-013,
  NSC-93-2422-H-001-0001, and NSC-93-2752-E-002-005-PAE.

A preliminary version: "The Min-Max Voronoi diagram of polygonal objects and
applications in VLSI manufacturing" appeared in Proc. 13th International
Symposium on Algorithms and Computation -- ISAAC'02, 
November 2002, Vancouver, Canada.

Abstract: 

We study the {\em Hausdorff Voronoi diagram} of a set $S$ of polygonal
objects in the plane, a generalization of Voronoi diagrams based on the
{\em maximum} distance  of a point from a polygon,  
and show that it is equivalent to the Voronoi diagram of $S$  under the 
{\em Hausdorff distance} function.
We investigate the structural and combinatorial properties of the
Hausdorff Voronoi diagram and give a divide and conquer algorithm for
the construction of this diagram that improves upon previous rsults. 
As a byproduct we introduce the {\em Hausdorff hull}, a structure that 
relates to the Hausdorff Voronoi diagram in the same way as a convex hull
relates to the ordinary Voronoi diagram.
The Hausdorff Voronoi diagram finds direct application in the problem
of computing the {\em critical area} of a VLSI Layout, a measure
reflecting the sensitivity of a VLSI design to random  manufacturing
defects,  described  in a ompanion paper  
[E. Papadopoulou, The  Hausdorff Voronoi diagram of point clusters in the
plane, Algorithmica, 40, 2004, 63-82].

Keywords: Voronoi diagram, Hausdorff distance, Hausdorff-hull, divide
     and conquer, VLSI yield, VLSI  critical area, via-block defects.

Int'l J. Comput. Geometry & Applications, (14,6):421-452, Dec. 2004.