Projekt

Zurück zur Übersicht

Hausdorff and Higher-Order Voronoi Diagrams

Gesuchsteller/in Papadopoulou Evanthia
Nummer 134355
Förderungsinstrument Projektförderung (spezial)
Forschungseinrichtung Facoltà di scienze informatiche Università della Svizzera italiana
Hochschule Università della Svizzera italiana – USI
Hauptdisziplin Informatik
Beginn/Ende 01.11.2011 - 30.04.2015
Bewilligter Betrag 295'050.00
Alle Daten anzeigen

Alle Disziplinen (2)

Disziplin
Informatik
Mathematik

Keywords (7)

Voronoi diagram; Hausdorff Voronoi diagram; order-k Voronoi diagram; line segments; Euclidean distance; L-infinity metric; abstract Voronoi diagram

Lay Summary (Englisch)

Lead
Lay summary

This project investigates fundamental open problems related to Hausdorff and higher-order Voronoi diagrams. Such Voronoi diagrams provide subdivisions of space into maximal regions that reveal important proximity information.  For example, higher-order Voronoi diagrams reveal k-nearest neighbor information. Hausdorff Voronoi diagrams reveal proximity information among clusters of objects, where distance between a point t and a cluster P is measured as the maximum among all objects in P, while distance between t and an object s is the ordinary minimum distance. The objective of the project is to derive a deeper understanding of these fundamental geometric structures, link them with the existing theoretical framework, and produce efficient, yet simple, algorithms for their construction. Diverse application areas can directly benefit from such algorithms. An example is the area of VLSI yield analysis and manufacturability, where generalized Voronoi diagrams of polygonal objects have already provided the basis of most advanced design automation tools in semiconductor industry.

Problems under investigation in this project include: The Hausdorff Voronoi diagram of clusters of line-segments, more generally, the Hausdorff Voronoi diagram of clusters of polygonal objects. New algorithms for the efficient construction of higher-order Voronoi diagrams for simple geometric objects such as points and line-segments. Combinatorial and algorithmic simplifications for higher-order and Hausdorff Voronoi diagrams in the computationally simpler, piecewise linear, L-infinity and L-1 metrics. The identification of common properties of various concrete Hausdorff and higher-order Voronoi diagrams with the goal of unifying their notion under the general concept of abstract Voronoi diagrams.   

Direktlink auf Lay Summary Letzte Aktualisierung: 21.02.2013

Verantw. Gesuchsteller/in und weitere Gesuchstellende

Mitarbeitende

Publikationen

Publikation
A Randomized Incremental Approach for the Hausdorff Voronoi Diagram of Non-crossing Clusters
Cheilaris P., Khramtcova E., Langerman S., Papadopoulou E. (2016), A Randomized Incremental Approach for the Hausdorff Voronoi Diagram of Non-crossing Clusters, in Algorithmica, 76(4), 935-960.
Layout pattern analysis using the Voronoi diagram of line segments
Dey S. K., Cheilaris P., Gabrani M., Papadopoulou E. (2016), Layout pattern analysis using the Voronoi diagram of line segments, in Journal of Micro/Nanolithography, MEMS, and MOEMS, 15(1), 013504.
Stabbing circles for sets of segments in the plane
Claverol M., Khramtcova E., Papadopoulou E., Saumell M., Seara C. (2016), Stabbing circles for sets of segments in the plane, in 12th Latin American Theoretical INformatics Symposium (LATIN), Ensenada, MexicoSpringer, LNCS 9644, Springer.
Linear-time algorithms for the farthest segment Voronoi diagram and related tree-structures
Khramtcova Elena, Papadopoulou Evanthia (2015), Linear-time algorithms for the farthest segment Voronoi diagram and related tree-structures, in 26th International Symposium on Algorithms and Computation (ISAAC), Nagoya, JapanSpringer, LNCS, Springer.
Linear-time algorithms for the farthest segment Voronoi diagram and related tree-structures
Khramtcova Elena, Papadopoulou Evanthia (2015), Linear-time algorithms for the farthest segment Voronoi diagram and related tree-structures, University of Ljubljana, Ljubljana, Slovenia.
On the complexity of higher order abstract Voronoi diagrams
Bohler C., Cheilaris P., Klein R., Liu C. H., Papadopoulou E., Zavershynskyi M. (2015), On the complexity of higher order abstract Voronoi diagrams, in Computational Geometry: Theory and Aplications, 48(8), 539-551.
Randomized incremental construction for the Hausdorff Voronoi diagram
Khramtcova Elena, Papadopoulou Evanthia (2015), Randomized incremental construction for the Hausdorff Voronoi diagram, in Young Researchers Forum: Book of Abstracts, Computational Geometry Week, 2015, Eindhoven, The NetherlandsAbstracts of Computational Geometry: Young Researchers Forum (CG:YRF)}, 2015, Eindhoven, Netherlands.
The k-Nearest-Neighbor Voronoi diagram revisited
Liu C.-H., Papadopoulou E., Lee D. T. (2015), The k-Nearest-Neighbor Voronoi diagram revisited, in Algorithmica, 71(2), 429.
Topology and context-based pattern extraction using line-segment Voronoi diagrams
Dey S. K., Cheilaris P., Casati N., Gabrani M., Papadopoulou E (2015), Topology and context-based pattern extraction using line-segment Voronoi diagrams, in SPIE Advanced Lithography, Design-Process-Technology Co-optimization for Man, SPIE, SPIE digital library, Volume 9427.
A randomized incremental approach for the Hausdorff Voronoi diagram of non-crossing clusters
Cheilaris Panagiotis, Khramtcova Elena, Langerman Stefan, Papadopoulou Evanthia (2014), A randomized incremental approach for the Hausdorff Voronoi diagram of non-crossing clusters, in LATIN 2014, Springer, LNCS 8392, Springer.
A Simple RIC for the Hausdorff Voronoi Diagram of Non-crossing Clusters
Khramtcova E., Papadopoulou E. (2014), A Simple RIC for the Hausdorff Voronoi Diagram of Non-crossing Clusters, in Abstracts of the 30th European Workshop on Computational Geometry (EuroCG), Ben-Gurion University , Israel.
A Subdivision Approach to Weighted Voronoi Diagrams
Bennett H., Papadopoulou E., Yap C. (2014), A Subdivision Approach to Weighted Voronoi Diagrams, University of Connecticut, http://fwcg14.cse.uconn.edu/program/.
Implementing the L_ınfinity segment Voronoi diagram in CGAL and applying in VLSI pattern analysis
Cheilaris P., Dey S. K., Gabrani M., Papadopoulou E. (2014), Implementing the L_ınfinity segment Voronoi diagram in CGAL and applying in VLSI pattern analysis, in 4th International Congress on Mathematical software (ICMS), LNCS, Springer, Springer, LNCS 8592.
On farthest-site Voronoi diagrams of line segments and lines in three and higher dimensions
Barequet G., Papadopoulou E. (2014), On farthest-site Voronoi diagrams of line segments and lines in three and higher dimensions, in Abstracts of the 30th European Workshop on Computational Geometry (EuroCG), Ben-Gurion University of the Negev, Israel.
On the complexity of higher order abstract Voronoi diagrams
Bohler C., Cheilaris P., Klein R., Liu C.-H., Papadopoulou E., Zavershynskyi M. (2013), On the complexity of higher order abstract Voronoi diagrams, in 40th International Colloquium on Automata, Languages and Programming (ICALP), LNCS 7965, Springer, LNCS 7965, Springer.
On the farthest Voronoi diagram of line segments in three dimensions
Barequet G., Papadopoulou E. (2013), On the farthest Voronoi diagram of line segments in three dimensions, in 10th International Symposium on Voronoi Diagrams in Science and Engineering (ISVD), St Petersburg, RussiaIEEE-CS, http://doi.ieeecomputersociety.org/10.1109/ISVD.2013.15.
Randomized incremental construction of the Hausdorff Voronoi diagram of non-crossing clusters
Cheilaris Panagiotis, Khramtcova Elena, Papadopoulou Evanthia (2013), Randomized incremental construction of the Hausdorff Voronoi diagram of non-crossing clusters, in 29th European Workshop on Computational Geometry (EuroCG), Braunschweig, GermanyTU Braunschweig, Braunschweig, Germany.
Stabbing circles for sets of segments in the plane
Khramtcova E., Papadopoulou E., Saumel M., Seara C., Stabbing circles for sets of segments in the plane, in Abstracts of the XVI Spanish Meeting on Computational Geometry (XVI EGC), Barcelona, SpainUniversitat Polite`cnica de Catalunya, Spain, http://dccg.upc.edu/egc15/en/wp-content/uploads/2013/10/AbstractsXVIEGC.pdf.

Zusammenarbeit

Gruppe / Person Land
Formen der Zusammenarbeit
Prof. Gill Barequet, Technion Israel (Asien)
- vertiefter/weiterführender Austausch von Ansätzen, Methoden oder Resultaten
- Publikation
Dr. Chih Hung Liu, University of Bonn Deutschland (Europa)
- vertiefter/weiterführender Austausch von Ansätzen, Methoden oder Resultaten
- Publikation
Prof. Rolf Klein, University of Bonn Deutschland (Europa)
- vertiefter/weiterführender Austausch von Ansätzen, Methoden oder Resultaten
- Publikation
- Austausch von Mitarbeitern
Dr. Maria Saumell, University of West Bohemia Tschechische Republik (Europa)
- vertiefter/weiterführender Austausch von Ansätzen, Methoden oder Resultaten
- Publikation
- Austausch von Mitarbeitern
Prof. Ferran Hurtado, DCCG group, UPC Spanien (Europa)
- vertiefter/weiterführender Austausch von Ansätzen, Methoden oder Resultaten
Prof. Carlos Seara, UPC Spanien (Europa)
- vertiefter/weiterführender Austausch von Ansätzen, Methoden oder Resultaten
- Publikation
- Austausch von Mitarbeitern

Wissenschaftliche Veranstaltungen

Aktiver Beitrag

Titel Art des Beitrags Titel des Artikels oder Beitrages Datum Ort Beteiligte Personen
12th Latin American Theoretical Informatics Symposium Vortrag im Rahmen einer Tagung Stabbing circles for sets of segments in the plane 11.04.2016 Ensenada, Mexiko Khramtcova Elena; Papadopoulou Evanthia;
26th International Symposium on Algorithms and Computation Vortrag im Rahmen einer Tagung Linear-time algorithms for the farthest segment Voronoi diagram and related tree-structures 14.12.2015 Nagoya, Japan Papadopoulou Evanthia;
31st European Workshop on Computational Geometry Vortrag im Rahmen einer Tagung Linear-time algorithms for the farthest segment Voronoi diagram and related tree-structures 15.03.2015 Ljubljana, Slowenien Papadopoulou Evanthia; Khramtcova Elena;
40th SPIE Advanced Lithography Symposium (Design-Process-Technology Co-optimization for Manufacturability IX Vortrag im Rahmen einer Tagung Topology and context-based pattern extraction using line-segment Voronoi diagrams 22.02.2015 San Jose, Vereinigte Staaten von Amerika Cheilaris Panagiotis; Papadopoulou Evanthia;
International Congress on Mathematical software (ICMS) Vortrag im Rahmen einer Tagung Implementing the L_infinity segment Voronoi diagram in CGAL and applying in VLSI pattern analysis 05.08.2014 Seoul, Korea, Republik (Südkorea) Cheilaris Panagiotis;
30th European Workshop on Computational Geometry Vortrag im Rahmen einer Tagung On farthest-site Voronoi diagrams of line segments and lines in three and higher dimensions 03.03.2014 Dead Sea, Israel Papadopoulou Evanthia;
30th European Workshop in Computational Geometry Vortrag im Rahmen einer Tagung A simple RIC for the Hausdorff Voronoi diagram of non-crossing clusters 02.03.2014 Dead Sea, Israel Khramtcova Elena;
ESF EuroGIGA Final Conference, Freie Universit\"{a}t Berlin Vortrag im Rahmen einer Tagung On Farthest, higher-order, and Hausdorff Voronoi diagrams. 17.02.2014 Berlin, Deutschland Khramtcova Elena; Papadopoulou Evanthia;
ESF EuroGIGA/VORONOI project annual meeting, Bonn, Germany September 2012. Vortrag im Rahmen einer Tagung The higher order Voronoi diagram of a planar straight line graph 23.09.2013 Bonn, Deutschland Papadopoulou Evanthia;
International Symposium on Voronoi Diagrams in Science and Engineering (ISVD) Vortrag im Rahmen einer Tagung On the farthest Voronoi diagram of line segments in three dimensions. 09.07.2013 St. Petersburg, Russland Papadopoulou Evanthia;
ESF ComPoSe-VORONOI EuroGIGA Meeting, Graz, Austria, July 2013. Vortrag im Rahmen einer Tagung On the Hausdorff Voronoi diagram of non-crossing clusters 09.07.2013 Graz, Oesterreich Cheilaris Panagiotis; Papadopoulou Evanthia;
35th CGAL Developer Meeting, May 2013 Vortrag im Rahmen einer Tagung Segment Delaunay graph L_infinity package development 27.03.2013 Nancy, Frankreich Cheilaris Panagiotis;
29th European Workshop in Computational Geometry (EuroCG) Vortrag im Rahmen einer Tagung Randomized incremental construction of the Hausdorff Voronoi diagram of non-crossing clusters. 25.03.2013 Braunschweig, Deutschland Papadopoulou Evanthia; Cheilaris Panagiotis;
Workshop on Geometric Computing Vortrag im Rahmen einer Tagung Efficient construction of the Hausdorff Voronoi diagram of non-crossing clusters 21.01.2013 Heraklion, Griechenland Papadopoulou Evanthia; Cheilaris Panagiotis;
Workshop on Geometric computing Vortrag im Rahmen einer Tagung Higher order and farthest Voronoi diagrams of line segments 21.01.2013 Heraklion, Griechenland Papadopoulou Evanthia;
ESF EuroGIGA Midterm Conference Vortrag im Rahmen einer Tagung The Hausdorff Voronoi diagram -- recent advances 09.07.2012 Charles University, Tschechische Republik Cheilaris Panagiotis; Papadopoulou Evanthia;
28th European Workshop in Computational Geometry, EuroCG 2012, and EuroGIGA meeting Vortrag im Rahmen einer Tagung On the farthest line-segment Voronoi diagram 21.03.2012 Assisi, Italien Cheilaris Panagiotis; Papadopoulou Evanthia;


Auszeichnungen

Titel Jahr
Luigi Franco Cerrina Memorial Best student Paper Award, SPIE Advanced Lithography 2015

Verbundene Projekte

Nummer Titel Start Förderungsinstrument
149658 Higher-order Voronoi Diagrams of Polygonal Objects 01.10.2013 Projektförderung (Abt. I-III)
154387 VORONOI++ 01.04.2016 Projektförderung (Abt. I-III)
127137 Generalized Voronoi Diagrams of Polygonal Objects: Algorithms and Applications 01.09.2010 Projektförderung (Abt. I-III)

Abstract

This project will investigate fundamental open problems related to Hausdorff and higher-order Voronoi diagrams. The objective is to derive a deeper understanding of these basic structures, link them with the existing theoretical framework, and produce efficient but simple algorithms for their construction. Diverse application areas, such as the area of VLSI yield analysis and design manufacturability (DFM), can directly benefit from such algorithms. Specifically, we plan to investigate the following problems:The Hausdorff Voronoi diagram of clusters of line-segments, more generally, the Hausdorff Voronoi diagram of clusters of polygonal objects, and abstract Hausdorff Voronoi diagrams. We will investigate different types of Hausdorff Voronoi diagrams, starting with the Hausdorff Voronoi diagram of clusters of line-segments. The Hausdorff Voronoi diagram of clusters of line segments is a natural generalization of the point cluster Hausdorff Voronoi diagram, which has been motivated by applications. In addition, we plan to investigate whether various Hausdorff Voronoi diagrams can be unified under a common abstract umbrella as ordinary Voronoi diagrams can. Abstract Voronoi diagrams are defined in terms of bisecting curves and they offer a unifying framework for many instances of concrete Voronoi diagrams.Higher order Voronoi diagrams. We plan to explore the tight connection between Hausdorff Voronoi diagrams and higher-order Voronoi diagrams with the purpose of deriving simpler algorithms (e.g., plane sweep) to compute higher-order Voronoi diagrams even for the standard case of points, and expand the results to more general types of objects. Higher-order Voronoi diagrams are natural generalizations of the classic Voronoi diagram. In addition, we plan to explore the problem of unifying various concrete higher order Voronoi diagrams under the unifying concept of abstract Voronoi diagrams, in collaboration with CRP partner Rolf Klein. Generalized Voronoi diagrams in simpler non-Euclidean (piecewise linear) metrics such as the L-infinity/ L-1 metrics. We plan to investigate possible simplifications in the structural complexity of generalized Voronoi diagrams in the L-infinity metric such as the farthest line segment Voronoi diagram, higher order Voronoi diagrams, and Hausdorff Voronoi diagrams. In addition, we plan to investigate software design and implementation issues for variants of L-infinity Voronoi diagrams. Ultimate goal (not explicitly included as a deliverable in this project) is the creation of open source code (CGAL based, http://www.cgal.org/) for the construction of different versions of generalized L-infinity Voronoi diagrams targeting VLSI applications.
-