Projekt

Zurück zur Übersicht

Generalized Voronoi Diagrams of Polygonal Objects: Algorithms and Applications

Gesuchsteller/in Papadopoulou Evanthia
Nummer 127137
Förderungsinstrument Projektförderung (Abt. I-III)
Forschungseinrichtung Facoltà di scienze informatiche Università della Svizzera italiana
Hochschule Università della Svizzera italiana – USI
Hauptdisziplin Informatik
Beginn/Ende 01.09.2010 - 30.09.2013
Bewilligter Betrag 157'692.00
Alle Daten anzeigen

Keywords (8)

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

Lay Summary (Englisch)

Lead
Lay summary
We will investigate open 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 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, 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. Generalized Voronoi diagrams of higher order-k generalize this notion to more than one site. They define a partitioning of space into maximal regions such that every point within a region has the same k nearest sites. The Hausdorff Voronoi diagram is another generalization of Voronoi diagrams, defined on clusters of points, where the distance between a point t and a cluster P is measured according to the maximum distance between t and all elements in P, and the Hausdorff Voronoi region of P is the locus of points closer to P than to any other cluster.In this project, we plan to investigate open questions related to the following problems: the higher order Voronoi diagram of line segments, the higher order Hausdorff Voronoi diagram, and the geometric min-cut problem. The geometric min cut problem is an interesting variant of the classic min cut problem in graphs and it is related to both Voronoi diagrams and graph connectivity. Our work will combine the combinatorial and structural analysis of these fundamental geometric structures, the design and analysis of efficient algorithms for their construction, as well as implementation and application issues. The problems under investigation are fundamental combinatorial structures central in the field of computational geometry that are interesting on their own right. In addition, they have been motivated by application problems and their solution can have direct impact on emerging CAD technologies for VLSI Manufacturability and other applications.
Direktlink auf Lay Summary Letzte Aktualisierung: 21.02.2013

Verantw. Gesuchsteller/in und weitere Gesuchstellende

Mitarbeitende

Publikationen

Publikation
On the farthest line-segment Voronoi diagram
Papadopoulou Evanthia, Dey Sandeep Kumar (2013), On the farthest line-segment Voronoi diagram, in International Journal of Computational Geometry and Applications, 23(6), 443-459.
A Sweepline Algorithm for Higher Order Voronoi Diagrams
Papadopoulou E., Zavershynskyi M. (2013), A Sweepline Algorithm for Higher Order Voronoi Diagrams, in 10th Int. Symp. on Voronoi Diagrams in Science and Engineering (ISVD) IEEE-CS, St. PetersburgIEEE-CS.
Map of Geometric Minimal Cuts with Applications
Papadopoulou Evanthia, Xu Jinhui, Xu Lei (2013), Map of Geometric Minimal Cuts with Applications, in P. M. Pardalos, R. Graham, D. Z. Du (ed.), Springer, Online, 27.
On higher-order Voronoi diagrams of line segments
Papadopoulou Evanthia, Zavershynsky Maksym (2012), On higher-order Voronoi diagrams of line segments, in 23rd International Symposium on Algorithms and Computation (ISAAC).
On the farthest line segment Voronoi diagram
Papadopoulou Evanthia, Dey Sandeep Kumar (2012), On the farthest line segment Voronoi diagram, in 23rd International Symposium on Algorithms and Computation (ISAAC).
The L_infinity (L_1) farthest line segment Voronoi diagram
Papadopoulou Evanthia, Dey Sandeep Kumar (2012), The L_infinity (L_1) farthest line segment Voronoi diagram, in 9th International Symposium on Voronoi Diagrams in Science and Engineering (ISVD).
Net-aware critical area extraction for opens in VLSI circuits via higher-order Voronoi diagrams
Papadopoulou Evanthia (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.
An Output-Sensitive Approach for the L_1/L_infinity k-Nearest-Neighbor Voronoi Diagram
Liu Chih-Hung, Papadopoulou Evanthia, Lee Der-Tsai (2011), An Output-Sensitive Approach for the L_1/L_infinity k-Nearest-Neighbor Voronoi Diagram, in 19th Annual European Symposium on Algorithms (ESA), 19th Annual European Symposium on Algorithms, ESA 2011, LNCS , Saarbr\"{u}cken, Germany.
The L_infinity Hausdorff Voronoi diagram revisited
Papadopoulou Evanthia, Xu Jinhui (2011), The L_infinity Hausdorff Voronoi diagram revisited, in Int. Symposium on Voronoi Diagrams in Science and Engineering (ISVD), Int. Symposium on Voronoi Diagrams in Science and Engineering, ISVD 2011, Qingdao, China.
Computing the Map of Geometric Minimal Cuts
Xu Jinhui, Xu Lei, Papadopoulou Evanthia, Computing the Map of Geometric Minimal Cuts, in Algorithmica.
The k-Nearest-Neighbor Voronoi diagram revisited
Liu Chih-Hung, Papadopoulou Evanthia, Lee D. T., The k-Nearest-Neighbor Voronoi diagram revisited, in Algorithmica.

Wissenschaftliche Veranstaltungen

Aktiver Beitrag

Titel Art des Beitrags Titel des Artikels oder Beitrages Datum Ort Beteiligte Personen
International Symposium on Voronoi Diagrams in Science and Engineering (ISVD) 2013 Vortrag im Rahmen einer Tagung A Sweepline Algorithm for Higher Order Voronoi Diagrams 08.07.2013 St. Petersburg, Russland Zavershynskyi Maksym; Papadopoulou Evanthia;
29th European Workshop in Computational Geometry (EuroCG) 2013 Vortrag im Rahmen einer Tagung A Sweepline Algorithm for Higher Order Voronoi Diagrams 17.03.2013 Braunschweig, Deutschland Papadopoulou Evanthia; Zavershynskyi Maksym;
23rd International Symposium on Algorithms and Computation (ISAAC) 2012 Vortrag im Rahmen einer Tagung On higher-order Voronoi diagrams of line segments 18.12.2012 Taipei, Taiwan Zavershynskyi Maksym;
23rd International Symposium on Algorithms and Computation (ISAAC) 2012 Vortrag im Rahmen einer Tagung On the farthest line-segment Voronoi diagram 17.12.2012 Taipei, Taiwan Papadopoulou Evanthia;
ESF EuroGIGA Midterm Conference, Charles University Vortrag im Rahmen einer Tagung On higher-order (and farthest) line segment Voronoi diagrams 09.07.2012 Prague, Tschechische Republik Papadopoulou Evanthia; Zavershynskyi Maksym;
International Symposium on Voronoi Diagrams in Science and Engineering (ISVD) 2012 Vortrag im Rahmen einer Tagung The L_infinity (L_1) farthest line segment Voronoi diagram 27.06.2012 Rutgers University, USA, Vereinigte Staaten von Amerika Papadopoulou Evanthia;
27th European Workshop in Computational Geometry (EuroCG) 2011 Vortrag im Rahmen einer Tagung The L_infinity Hausdorff Voronoi diagram revisited 19.03.2012 Morschach, Switzerland , Schweiz Papadopoulou Evanthia;
28th European Workshop in Computational Geometry (EuroCG) 2012 Vortrag im Rahmen einer Tagung On higher-order Voronoi diagrams of line segments 19.03.2012 Assisi, Italy, Italien Papadopoulou Evanthia; Zavershynskyi Maksym;
28th European Workshop in Computational Geometry (EuroCG) 2012 Vortrag im Rahmen einer Tagung On the farthest line-segment Voronoi diagram 19.03.2012 Assisi, Italien Papadopoulou Evanthia;
19th Annual European Symposium on Algorithms (ESA) 2011 Vortrag im Rahmen einer Tagung An Output-Sensitive Approach for the L_1/L_infinity k-Nearest-Neighbor Voronoi Diagram 05.09.2011 Saarbr\"{u}cken, Germany,, Deutschland Papadopoulou Evanthia;
International Symposium on Voronoi Diagrams in Science and Engineering (ISVD) 2011 Vortrag im Rahmen einer Tagung The L_infinity Hausdorff Voronoi diagram revisited 28.06.2011 Qingdao, China, China Papadopoulou Evanthia;


Verbundene Projekte

Nummer Titel Start Förderungsinstrument
149658 Higher-order Voronoi Diagrams of Polygonal Objects 01.10.2013 Projektförderung (Abt. I-III)
134355 Hausdorff and Higher-Order Voronoi Diagrams 01.11.2011 Resource not found: '14158e84-cfda-4226-8c85-fbd83c4bfc8f'

Abstract

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