Projekt

Zurück zur Übersicht

Higher-order Voronoi Diagrams of Polygonal Objects

Gesuchsteller/in Papadopoulou Evanthia
Nummer 149658
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.10.2013 - 31.12.2014
Bewilligter Betrag 57'160.00
Alle Daten anzeigen

Keywords (5)

polygonal objects; Higher-order Voronoi diagrams; Computational Geometry; Design and Analysis of Algorithms; Voronoi Diagrams

Lay Summary (Italienisch)

Lead
I Diagrammi di Voronoi hanno dimostrato di essere potenti strumenti per risolvere diversi e apparentemente scollegati problemi computazionali. Il concetto di base è semplice: dato un numero di siti nel piano, il diagramma di Voronoi divide lo spazio in regioni, tali che la regione di Voronoi di un sito s è il luogo dei punti più vicini ad s rispetto a qualsiasi altro sito. Questo progetto studierà i diagrammi di Voronoi di ordine superiore di oggetti poligonali.
Lay summary

I Diagrammi di Voronoi possono essere definiti per "siti" che sono punti, segmenti, oggetti poligonali, o altri tipi di oggetti geometrici. In molti casi di pratica importanza, la geometria di un problema è modellata da oggetti poligonali. A questo proposito, i diagrammi di Voronoi generalizzati di oggetti poligonali sono di particolare importanza. I Diagrammi di Voronoi di ordine superiore codificano l'informazione K-nearest-neighbor e definiscono una suddivisione dello spazio in regioni massimali tali che ogni punto all'interno di una regione ha la stessa misura K-nearest-neighbor. L'obiettivo principale di questo progetto è la progettazione di algoritmi efficienti per costruire il diagramma di Voronoi di ordine-K di segmenti lineari e più in generale, poligoni convessi. Questo progetto si baserà sul nostro precedente lavoro sulla derivazione delle proprietà combinatorie e strutturali dei diagrammi di Voronoi di ordine k di segmenti lineari, inclusi segmenti lineari disgiunti o intersecanti, così come segmenti di linea che formano grafi planari di linee rette.
Il lavoro è importante sia da un punto di vista teorico che applicativo dato che indaga strutture geometriche fondamentali al centro della disciplina della geometria computazionale, la cui giustificazione pratica è già stata provata da applicazioni industriali in VLSI Design Automation; ne consegue che l'indagine su tali strutture può avere un impatto diretto e significativo su tecnologie CAD per la produzione di semiconduttori. 

Direktlink auf Lay Summary Letzte Aktualisierung: 30.09.2013

Verantw. Gesuchsteller/in und weitere Gesuchstellende

Mitarbeitende

Publikationen

Publikation
The L_infinity Hausdorff Voronoi diagram revisited
Papadopoulou Evanthia, Xu Jinhui (2015), The L_infinity Hausdorff Voronoi diagram revisited, in International Journal of Computational Geometry and Applications, 25(2), 123-141.
A Randomized Divide and Conquer Algorithm for Higher-Order Abstract Voronoi Diagrams
Bohler Cecilia, Liu Chih-Hung, Papadopoulou Evanthia, Zavershynskyi Maksym (2014), A Randomized Divide and Conquer Algorithm for Higher-Order Abstract Voronoi Diagrams, in 25th International Symposium on Algorithms and Computation (ISAAC), Jeonju, South KoreaLecture Notes in Computer Science, 8889, Springer.
The Higher-Order Voronoi Diagram of Line Segments
Papadopoulou Evanthia, Zavershynskyi Maksym, The Higher-Order Voronoi Diagram of Line Segments, in Algorithmica.

Zusammenarbeit

Gruppe / Person Land
Formen der Zusammenarbeit
University of Bonn Deutschland (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
25th International Symposium on Algorithms and Computation (ISAAC) Vortrag im Rahmen einer Tagung A randomized divide and conquer algorithm for higher-order abstract Voronoi diagrams 15.12.2014 Jeonju, Korea, Republik (Südkorea) Papadopoulou Evanthia;
ESF EuroGIGA Final Conference, Freie Universit\"{a}t Berlin Vortrag im Rahmen einer Tagung Randomized algorithms for higher-order Voronoi diagrams 17.02.2014 Berlin, Deutschland Zavershynskyi Maksym; Papadopoulou Evanthia;
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 Papadopoulou Evanthia; Zavershynskyi Maksym;


Verbundene Projekte

Nummer Titel Start Förderungsinstrument
127137 Generalized Voronoi Diagrams of Polygonal Objects: Algorithms and Applications 01.09.2010 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 closer 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. Higher order Voronoi diagrams (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, generalized Voronoi diagrams of polygonal objects are of particular importance.This project continues the investigation of higher order Voronoi diagram of polygonal objects that started in SNF project 200021-127137. The goal is the design of efficient algorithms to construct the order-k Voronoi diagram of such objects, including line segments and convex polygons. Polygons, introduce complications that are not present in the case of points or even line-segments. For example, the bisector of two convex polygons may be undefined, and the bisector of two simple polygons may be a closed curve. Higher order Voronoi diagrams under these conditions have not been considered in the computational geometry literature.The work is important from both a theoretical and an application point of view as it investigates fundamental geometric structures, central in the field of computational geometry, which have been motivated by industrial applications in VLSI Design Automation and may have direct impact to CAD technologies for semiconductor manufacturing.
-