## Kontakt

Schweizerischer Nationalfonds (SNF)

Wildhainweg 3Postfach

CH-3001 Bern

Tel. +41 31 308 22 22

Fax +41 31 301 30 09

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 |

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

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 |

Name | Institut |
---|

Name | Institut |
---|

Publikation |
---|

On the farthest line-segment Voronoi diagram |

Net-aware critical area extraction for opens in VLSI circuits via higher-order Voronoi diagrams |

An Output-Sensitive Approach for the L_1/L_infinity k-Nearest-Neighbor Voronoi Diagram |

The L_infinity Hausdorff Voronoi diagram revisited |

On higher-order Voronoi diagrams of line segments |

On the farthest line segment Voronoi diagram |

The L_infinity (L_1) farthest line segment Voronoi diagram |

A Sweepline Algorithm for Higher Order Voronoi Diagrams |

Map of Geometric Minimal Cuts with Applications |

The k-Nearest-Neighbor Voronoi diagram revisited |

Computing the Map of Geometric Minimal Cuts |

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 |

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 |

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 |

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 |

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 | Projektförderung (spezial) |

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.

Schweizerischer Nationalfonds (SNF)

Wildhainweg 3Postfach

CH-3001 Bern

Tel. +41 31 308 22 22

Fax +41 31 301 30 09

Gesuche eingeben und verwalten

E-Mail eintragen und Sie erhalten regelmässig den SNF-Newsletter

© SNF 2016