VORONOI++ - VORONOI++

Questo progetto studia una versatile struttura chiamata "diagramma di Voronoi", che rappresenta l'influenza che un dato insieme di luoghi (o posti, o siti) esercitano sullo spazio circostante. Questo tipo di strutture che partizionano lo spazio è conosciuto fin dal 17° secolo e il loro utilizzo nella soluzione di problemi spazio-geometrici è stato coronato da numerosi successi. Nel nostro progetto, studieremo i "cluster Voronoi diagrams", dove i siti sono insiemi (clusters) di semplici oggetti geometrici nel piano. Questi diagrammi generano delle divisioni del piano, dove ogni regione esalta delle informazioni di prossimità per i clusters dati o per i clusters dei siti in ingresso.

Nel nostro programma investigheremo alcuni problemi aperti relativi al "farthest color Voronoi diagram" (FCVD), al "Hausdorff Voronoi diagram" (HVD) e al Voronoi diagram di ordine k, incluso il "farthest-site Voronoi diagram" (con k = n - 1).

Tra gli obiettivi:

* identificare le condizioni per cui il FCVD è un "albero" o ha complessità combinatoria lineare e costruire algoritmi efficienti per la sua costruzione;

* investigare vari algoritmi per calcolare FCVD e HVD nella loro generalità;

* definire il diagramma di Voronoi (colorato) di ordine k di clusters e identificarne casi speciali d'interesse;

* investigare algoritmi lineari per costruire diagrammi di Voronoi quasi arborescenti (quali quelli che appaiono nei diagrammi di ordine k e “farthest”).

Contesto socio-scientifico

Il diagramma di Voronoi è una struttura nota e pervasiva nelle scienze, in ingegneria e in economia. I problemi che studieremo hanno origine in applicazioni di logistica, reti wireless di sensori e VLSI design. Questo progetto accrescerà le nostre conoscenze su questo versatile oggetto matematico e i risultati potranno avere un impatto in tutti i campi di applicazione succitati.