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 nearest sites.

Our project is funded by SNF (under project number 127137).

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 Foundation (ESF).

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.

CGAL implementation

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)

An interesting future work would be to derive an optimal set of Patterns for model-based OPC (Optical Proximity Correction).