Voronoi diagrams of polygonal objects
We investigate problems on
generalized Voronoi diagrams of
polygonal objects in the plane. Voronoi diagrams are among the most
fundamental structures in Computational Geometry and they have proved
powerful tools in solving diverse
computational problems. The standard Voronoi diagram of a set of sites
in the plane is a subdivision of the plane into
regions such that the Voronoi region of a site p is the locus of
points closest to p than to any other site.
Sites can be points,
polygonal objects, or other types of geometric objects.
Higher order Voronoi diagrams encode k-nearest
neighbor information and they define a partitioning of space into
maximal regions such that every point within a region has the same k
Our project is funded by SNF (under project
Hausdorff and higher order Voronoi diagrams
Spacial Decompositions and Graphs (short nickname: VORONOI) is a
collaborative research project. It involves 8 partners from 6 different
countries, and it is part of the EuroGIGA program of the European Science
Our group, in particular, investigates problems related to Hausdorff and
higher-order Voronoi diagrams in the plane. The objective is to derive a
deeper understanding of these fundamental geometric structures, link them
with the existing theoretical framework, and produce efficient but simple
algorithms for their construction. Diverse application areas can directly
benefit from such algorithms. An example is the area of VLSI yield analysis
and design manufacturability (DFM), where generalized Voronoi diagrams of
polygonal objects have already provided the basis of most advanced design
automation tools in the semiconductor industry.
Our individual subproject is funded jointly by SNF (under project
number 134355) and ESF.
Cluster Voronoi diagrams
Voronoi diagram of a set of sites is a subdivision of a space into maximal regions
according to the closeness relation with respect to sites.
Voronoi diagram of a set of points in the plain looks like this:
This diagram is widely used in different areas, since it allows answering the proximity queries efficiently.
However, approximating the real objects as points is often not precise enough. Then the generalized Voronoi diagrams come into play.
Our research is focused on the cases when the sites are sets of points instead of single points (Hausdorff Voronoi diagram of point-clusters, Farthest Color Voronoi diagram, farthest Voronoi diagram of line segments). For example, here is the set of clusters and its Hausdorff Voronoi diagram and Farthest Color Voronoi diagram respectively:
For those structures we are seeking for efficient construction algorithms. Applying the known techniques becomes challenging since those Voronoi diagrams have properties, substantially different from the standard case.
Another fascinating and mainly unexplored direction of research is moving from 2D to 3D. We study the farthest Voronoi diagram of line-segments and lines in 3D. The figures below depict a cross-section of these two diagrams by a sphere of a big radius. We call such cross-section a Gaussiam Map, and use it to analyze the behavior of the diagram close to infinity.
Computational Geometry Algorithm Library (CGAL
is a proven industrial standard tool to solve geometric problems in various application domain such as image processing, geometric modelling, EDA etc. The geometric algorithms and data structures in CGAL are implemented under the design goals of robustness, genericity, flexibility, efficiency, and ease of use. These design goals are fulfilled in CGAL by choosing C++ generic programming, using template classes, and function templates.
Our interest is to implement different variants of Voronoi diagram for line segments in the max-norm.
The existing segment Voronoi diagram in CGAL is for Euclidean metric and is constructed by a randomised incremental algorithm. There are two template parameters passed to the algorithm in this package, First is the geometric traits class that provides the basic geometric objects (points, segments, parabolic bisectors), the geometric predicates for computing the diagram such as in-circle tests, conflict tests etc. and some basic constructions for visualization of the diagram, and the Second is the triangulation data structure in CGAL for storing the diagram. We exploited the generic implementation of the segment Voronoi diagram in CGAL to write the trait classes for the implementation of the Voronoi diagram in the max-norm that is in a simple piece-wise linear metric. Some interesting challenges were to handle in-square tests, 2-dimensional bisectors, and the max-norm parabolae. The package is integrated with CGAL-4.7. Details can be found here
We are also interested in other implementation projects in the CGAL environment:
1. Plane sweep algorithm for construction of Voronoi diagrams.
2. Implementing higher order Voronoi diagrams.
VLSI pattern analysis
With the increase in miniaturization of current VLSI patterns, there is a significant rise in printability problems of such patterns, during the photolithography process. The analysis of patterns to find faults or error-prone locations, is of prime importance to the manufacturing process.
We have introduced a fast method to automatically extract patterns based on their structure and context, using the Voronoi diagram of VLSI design shapes. We first identified possible problematic locations, represented as gauge centers, and then use the derived locations to extract windows and problematic patterns from the design layout. The problematic locations are prioritized by the shape and proximity information of design polygons.
Our work on VLSI pattern analysis has won the Luigi Franco Cerrina Memorial Best Student Paper Award
at SPIE Advanced Lithography, Design-Process-Technology Co-optimization for Manufacturability IX, 2015. (pdf