The Hausdorff Voronoi Diagram of Polygonal Objects: A Divide and Conquer Approach
Resource
International Journal of Computational Geometry and Applications,14(6),421-452.
Journal
International Journal of Computational Geometry & Applications
Pages
421-452
Date Issued
2004-12
Date
2004-12
Author(s)
Papadopoulou, E.
Lee, D. T.
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
SDGs
Type
journal article
File(s)![Thumbnail Image]()
Loading...
Name
912.pdf
Size
361.82 KB
Format
Adobe PDF
Checksum
(MD5):fb72c6b84bf85e677628b720a8c14b3f