Name
Abstract | ||
|---|---|---|
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 S 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). |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1142/S0218195904001536 | INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS |
Keywords | DocType | Volume |
Voronoi diagram, Hausdorff distance, Hausdorff-hull, divide and conquer, VLSI yield, VLSI critical area, via-block defects | Journal | 14 |
Issue | ISSN | Citations |
6 | 0218-1959 | 9 |
PageRank | References | Authors |
0.59 | 10 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Evanthia Papadopoulou | 1 | 110 | 18.37 |
| D. T. Lee | 2 | 2418 | 1083.30 |