Higher-order Voronoi Diagrams of Polygonal Objects

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.