Heng Cao, Haifeng Xi, et al.
WSC 2003
We study the Hausdorff Voronoi diagram of a set S of polygonal objects in the plane, a generalization of Voronoi diagrams based on the maximum distance of a point from a polygon, and show that it is equivalent to the Voronoi diagram of 5 under the 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 results. As a byproduct we introduce the 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 critical area of a VLSI Layout, a measure reflecting the sensitivity of a VLSI design to random manufacturing defects, described in a companion paper.13 © World Scientific Publishing Company.
Heng Cao, Haifeng Xi, et al.
WSC 2003
Shashanka Ubaru, Lior Horesh, et al.
Journal of Biomedical Informatics
Daniel J. Costello Jr., Pierre R. Chevillat, et al.
ISIT 1997
Nimrod Megiddo
Journal of Symbolic Computation