Projekt

Zurück zur Übersicht

VORONOI++

Titel Englisch VORONOI++
Gesuchsteller/in Papadopoulou Evanthia
Nummer 154387
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.04.2016 - 31.03.2019
Bewilligter Betrag 198'008.00
Alle Daten anzeigen

Alle Disziplinen (2)

Disziplin
Informatik
Mathematik

Keywords (9)

Computational Geometry; Geometric Data Structures; Voronoi Diagrams; computational geometry; Voronoi diagrams; order-k and farthest Voronoi diagrams; farthest color Voronoi diagram; Hausdorff Voronoi diagram; tree-like Voronoi diagrams

Lay Summary (Italienisch)

Lead
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.
Lay summary

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.

 

Direktlink auf Lay Summary Letzte Aktualisierung: 23.02.2016

Verantw. Gesuchsteller/in und weitere Gesuchstellende

Mitarbeitende

Name Institut

Verbundene Projekte

Nummer Titel Start Förderungsinstrument
134355 Hausdorff and Higher-Order Voronoi Diagrams 01.11.2011 Resource not found: '14158e84-cfda-4226-8c85-fbd83c4bfc8f'

Abstract

This project is concerned with a versatile structure called the Voronoi diagram, which illustrates the influence that a given set of geometric sites exert on their surrounding space. Space-partitioning structures of this kind have been known since the 17th century, and they have successfully been applied to solve spatial problems.In this project, we focus on “cluster Voronoi diagrams”, where sites are sets (clusters) of simple geometric objects in the plane. Such diagrams provide subdivisions of the plane into maximal regions such that each region reveals proximity information for the input clusters or for clusters of the input sites. We plan to investigate open problems related to the so called farthest color Voronoi diagram (FCVD), the Hausdorff Voronoi diagram (HVD), and the order-k Voronoi diagram, including the farthest-site Voronoi diagram (where k = n – 1). Open problems include the following: Identifying conditions under which the FCVD is a tree structure, or it has linear combinatorial complexity, and design efficient algorithms to construct it.Investigate algorithms for computing the FCVD and HVD in their generality. Define the order-k color Voronoi diagram of a given family of clusters.Investigate linear-time construction algorithms for tree-like Voronoi diagrams (like those that appear in order-k and farthest diagrams).The Voronoi diagram is an influential structure playing an important role in natural sciences, economics, and engineering. This project will increase our knowledge on this powerful geometric object. The problems that we plan to investigate in this project stem out of applications related to facility location, wireless sensor networks, and VLSI design.
-