Generalized Voronoi Diagrams of Polygonal Objects: Algorithms and Applications

Voronoi diagrams are among the most fundamental structures in Computational Geometry and they have proved to be powerful tools in solving diverse and seemingly unrelated computational problems. The basic concept is simple: given a number of sites in the plane (or in any dimensional space) their Voronoi diagram divides the space into regions such that the Voronoi region of a site s is the locus of points closest to s than to any other site. Sites can be points, polygonal objects, or any other type of geometric object. Voronoi diagrams can be defined over any metric and in any dimension. Generalized Voronoi diagrams of order-k 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. Geometric scenarios occurring in practice are often modeled by polygonal objects. In this respect, Voronoi diagrams of polygonal objects are of particular importance. This proposal targets open problems on generalized Voronoi diagrams of polygonal objects. The problems we propose to study are fundamental combinatorial structures interesting on their own right; in addition, their solution can have direct impact on emerging CAD technologies for VLSI Manufacturability and other applications, see e.g. [36] for an important application in semiconductor yield analysis. The problems we propose to investigate include: the higher order line-segment Voronoi diagram, the higher order Hausdorff Voronoi diagram, the geometric min-cut problem, and kinetic or dynamic Voronoi diagrams of polygons under movement of their edges. Definitions of these problems are given in Section 2. Our proposed work includes the following: 1. Combinatorial and structural analysis of the these fundamental geometric structures.2. The design and analysis of efficient algorithms for the construction of these structures. 3. The analysis of robustness and implementation issues associated with those algorithms. This includes analysis of the algorithmic degree of the proposed algorithms and potential simplifications that target the motivating application. 4. Robust implementation in metrics appropriate for the motivating application.This work is important from both a theoretical and an application point of view as it will investigate fundamental geometric structures central in the field of computational geometry that may also have direct impact in industrial applications related to semiconductor manufacturing. The applicant is well positioned to pursue these lines of research as she already has been working at the forefront of this field for more than 10 years. The work of Evanthia Papadopoulou in recent years has combined the modeling of application problems in graph theoretic and geometric terms, the design and analysis of efficient algorithms to solve these problems independently, and the development of industrial CAD tools to tackle these problems in practice.