Paper Info
Title
The Hausdorff Voronoi Diagram of Point Clusters in the Plane
Abstract
We study the Hausdorfi Voronoi diagram of point clusters in the plane, a generalization of Voronoi diagrams based on the Hausdorfi 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 Hausdorfi 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 segments1 between pairs of crossing clusters2 . The plane sweep algorithm generalizes the standard plane sweep paradigm for the construction of Voronoi diagrams with the ability to handle disconnected Hausdorfi Voronoi regions. The Hausdorfi Voronoi diagram flnds direct application in the problem of computing the critical area of a VLSI Layout, a measure re∞ecting the sensitivity of the VLSI design to spot defects during manufacturing.
Year
DOI
Venue
2003
https://doi.org/10.1007/s00453-004-1095-0
Algorithmica
Keywords
Field
DocType
Voronoi diagram,Hausdorff distance,Plane sweep,VLSI yield prediction,VLSI Critical Area,Manufacturing defects,Via-blocks
Hausdorff dimension,Discrete mathematics,Power diagram,Topology,Combinatorics,Centroidal Voronoi tessellation,Mathematical diagram,Weighted Voronoi diagram,Voronoi diagram,Voronoi deformation density,Sweep line algorithm,Mathematics
Conference
Volume
Issue
ISSN
40
2
0178-4617
Citations 
PageRank 
References 
9
0.64
13
Authors
1
Name
Order
Citations
PageRank
Evanthia Papadopoulou111018.37