Voronoi diagrams in the max-norm: Algorithms, implementation, and applications

Staff - Faculty of Informatics

Start date: 16 June 2015

End date: 17 June 2015

You are cordially invited to attend the PhD Dissertation Defense of Sandeep Kumar DEY on Tuesday, June 16th 2015 at 15h30 in room SI-008 (Informatics building)
 
Abstract:
Voronoi diagrams and their numerous variants are well-established objects in computational geometry. They have proven to be extremely useful in the algorithmic and combinatorial analysis of geometric problems in various domains such as VLSI CAD, Computer Graphics, Pattern Recognition, Information Retrieval, etc. In this dissertation, we study generalized Voronoi diagram of line segments that have been motivated by applications in VLSI Computer Aided Design. The focus is on the L∞ metric. Our work has three directions: algorithms, implementation, and applications of the line-segment Voronoi diagrams. Results are as follows:
(1) Algorithms for the farthest Voronoi diagram of line segments in the Lp metric, 1 ≤ p ≤ ∞. Our main interest is the L2 (Euclidean) and the L∞ metric. The focus of this dissertation is in the L∞ metric. We first introduce the farthest line-segment hull and its Gaussian map to characterize the regions of the farthest line-segment Voronoi diagram at infinity. We then adapt well-known techniques for the construction of a convex hull to compute the farthest line-segment hull, and therefore, the farthest segment Voronoi diagram. Our approach unifies techniques to compute farthest Voronoi diagrams for points and line segments.
(2) The implementation of the L∞ nearest neighbor Voronoi diagram of line segments in the Computational Geometry Algorithms Library (CGAL). Our software (approximately 17K lines of C++ code) is built on top of the existing CGAL package on the L2 (Euclidean) Voronoi diagram of line segments. It has been submitted for inclusion in the CGAL library. We performed the implementation in the L∞ metric because we target applications in VLSI design, where shapes are predominantly rectilinear, and the L∞ segment Voronoi diagram is computationally simpler.
(3) The application of our Voronoi software to tackle proximity-related problems in VLSI pattern analysis. In particular, we use the Voronoi diagram to identify critical locations in patterns of VLSI layout, which can be faulty during the printing process of a VLSI chip. The patterns are verified using standard VLSI CAD tools for pattern verification. We present experiments involving layout pieces that were provided by IBM Research, Zürich. Our Voronoi-based method was able to find all problematic locations in the provided layout pieces, very fast, and without any manual intervention.

Dissertation Committee:

  • Prof. Evanthia Papadopoulou, Università della Svizzera italiana, Switzerland (Research Advisor)
  • Prof. Michael Bronstein, Università della Svizzera italiana, Switzerland (Internal Member)
  • Prof. Kai Hormann, Università della Svizzera italiana, Switzerland (Internal Member)
  • Prof. Gill Barequet, Technion, Israel Institute of Technology, Israel (External Member)
  • Prof. Menelaos Karavelas, University of Crete, Greece (External Member)