Design and Analysis of Algorithms; Computational Geometry; Generalized Voronoi Diagrams; VLSI Design for Manufacturability (DFM); Voronoi diagrams; geometric min cuts; Hausdorff Voronoi diagrams; higher order Voronoi diagrams
(2013), On the farthest line-segment Voronoi diagram, in International Journal of Computational Geometry and Applications
, 23(6), 443-459.
(2013), A Sweepline Algorithm for Higher Order Voronoi Diagrams, in 10th Int. Symp. on Voronoi Diagrams in Science and Engineering (ISVD) IEEE-CS
, St. Petersburg.
(2013), Map of Geometric Minimal Cuts with Applications, 27.
(2012), On higher-order Voronoi diagrams of line segments, in 23rd International Symposium on Algorithms and Computation (ISAAC)
(2012), On the farthest line segment Voronoi diagram, in 23rd International Symposium on Algorithms and Computation (ISAAC)
(2012), The L_infinity (L_1) farthest line segment Voronoi diagram, in 9th International Symposium on Voronoi Diagrams in Science and Engineering (ISVD)
(2011), Net-aware critical area extraction for opens in VLSI circuits via higher-order Voronoi diagrams, in IEEE Transactions on Computaer-Aided Design of Integrated Circuits and Systems
, 30(5), 704-716.
(2011), An Output-Sensitive Approach for the L_1/L_infinity k-Nearest-Neighbor Voronoi Diagram, in 19th Annual European Symposium on Algorithms (ESA)
(2011), The L_infinity Hausdorff Voronoi diagram revisited, in Int. Symposium on Voronoi Diagrams in Science and Engineering (ISVD)
, Computing the Map of Geometric Minimal Cuts, in Algorithmica
, The k-Nearest-Neighbor Voronoi diagram revisited, in Algorithmica
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.  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.