Ricerca di contatti, progetti,
corsi e pubblicazioni

Higher-order Voronoi Diagrams of Polygonal Objects

Persone

 

Papadopoulou E.

(Responsabile)

Zavershynskyi M.

(Collaboratore)

Abstract

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.

Informazioni aggiuntive

Data d'inizio
01.10.2013
Data di fine
31.12.2014
Durata
15 Mesi
Enti finanziatori
SNSF
Stato
Concluso
Categoria
Swiss National Science Foundation / Project Funding / Division II - Mathematics, Natural and Engineering Sciences