# Diagramma di Voronoi

In matematica, un diagramma di Voronoi (dal nome di Georgij Voronoi), anche detto tassellatura, partizione o decomposizione di Voronoi, o tassellatura di Dirichlet (dal nome di Lejeune Dirichlet) è un particolare tipo di decomposizione di uno spazio metrico determinata dalle distanze rispetto ad un determinato insieme discreto di elementi dello spazio (ad esempio, un insieme finito di punti).
Nel caso più semplice e comune, quello del piano, dato un insieme finito di punti $S$, il diagramma di Voronoi per $S$ è la partizione del piano che associa una regione $V(p)$ ad ogni punto $p\in S$ in modo tale che tutti i punti all'interno del perimetro di $V(p)$ siano più vicini a $p$ che a ogni altro punto in $S$.

## Definizione

In ogni insieme (topologicamente) discreto $S$ di punti in uno spazio euclideo e per quasi ogni punto $x$, c'è un punto in $S$ che è il più vicino a $x$. Il "quasi" è una precisazione necessaria dato che alcuni punti $x$ possono essere equidistanti da 2 o più punti di $S$.
Se $S$ contiene solo due punti, $a$ e $b$, allora il luogo geometrico dei punti equidistanti da $a$ e $b$ è un iperpiano, ossia un sottospazio affine di codimensione 1. Tale iperpiano sarà il confine tra l'insieme di tutti punti più vicini ad $a$ che a $b$ e l'insieme di tutti i punti più vicini a $b$ che ad $a$. È l'asse del segmento $ab.$
In generale, l'insieme dei punti più vicini a un punto $c\in S$ che ad ogni altro punto di $S$ è la parte interna di un politopo (eventualmente privo di bordi) detto dominio di Dirichlet o cella di Voronoi di $c.$ L'insieme di tali politopi è una tassellatura dell'intero spazio e viene detta tassellatura di Voronoi corrispondente all'insieme $S$. Se la dimensione dello spazio è solo 2, è facile rappresentare graficamente le tassellazioni di Voronoi; è a questo caso che si riferisce solitamente l'accezione diagramma di Voronoi.

## Proprietà

* Il grafo duale per un diagramma di Voronoi corrisponde alla triangolazione di Delaunay rispetto allo stesso insieme di punti $S$.
* La coppia di punti più ravvicinati di $S$ corrisponderà ad una coppia di celle di Voronoi adiacenti in un diagramma di Voronoi.
* Due punti sono vertici adiacenti dell'inviluppo convesso di $S$ se e solo se le loro celle di Voronoi hanno in comune un lato infinito.

## Storia

L'utilizzo informale dei diagrammi di Voronoi può essere fatto risalire a Cartesio nel 1644. Dirichlet utilizzò diagrammi di Voronoi bidimensionali e tridimensionali nei suoi studi delle forme quadratiche, nel 1850. Il medico britannico John Snow utilizzò un diagramma di Voronoi nel 1854 per illustrare come la maggioranza delle persone morte nell'epidemia di colera a Soho viveva più vicino ad una delle pompe infette di Broad Street che ad ogni altra pompa d'acqua.
I diagrammi di Voronoi traggono il loro nome dal matematico russo Georgii Fedoseevich Voronoi che definì e studiò il caso generale $n$-dimensionale nel 1908. I diagrammi di Voronoi che trovano applicazione in geofisica e in meteorologia per analizzare dati distribuiti spazialmente (come ad esempio misure delle precipitazioni) sono detti poligoni di Thiessen, dal nome del meteorologo americano Alfred H. Thiessen. In fisica della materia condensata, tali tassellazioni sono anche note come celle di Wigner-Seitz. Le tassellazioni di Voronoi del reticolo reciproco delle quantità di moto sono dette zone di Brillouin. Per reticoli generali nei gruppi di Lie, le celle sono semplicemente dette domini fondamentali. In spazi metrici generici, le celle sono spesso dette poligoni fondamentali.

## Esempi

Molte tassellazioni di Voronoi di griglie regolari di punti in due o tre dimensioni risultano essere tassellazioni familiari:
* una griglia bidimensionale triangolare produce una tassellazione di esagoni, che saranno regolari se i punti della griglia sono vertici di triangoli equilateri; una griglia rettangolare avrà a sua volta un diagramma di Voronoi composto da rettangoli, che saranno inoltre quadrati se la griglia era quadrata.
* Due griglie bidimensionali triangolari regolari opportunamente allineate su due piani paralleli producono la configurazione di prismi esagonali con rombi alle estremità che si può osservare negli alveari.
* Supponendo di tassellare lo spazio con dei cubi, la griglia ottenuta ponendo un punto al centro di ogni faccia di un cubo produce come diagramma di Voronoi una tassellatura di dodecaedri rombici.
* Se invece i punti vengono messi al "centro" di ogni cubo, si ottiene una tassellazione composta di ottaedri tronchi.
Tornando nel piano, dati due insiemi $X,Y$ discreti di numeri reali, il diagramma di Voronoi relativo all'insieme $\{(x,y)\mid x\in X,y\in Y\}$ produce una tassellatura composta da rettangoli (i cui punti non sono necessariamente i centri).

## Generalizzazioni

Le celle di Voronoi possono essere definite in metriche non euclidee (come la distanza di Mahalanobis o quella della geometria del taxi). Ciononostante in tali casi non è garantito che la tassellazione di Voronoi esista (o che sia una tassellazione), dato che il luogo dei punti equidistanti da due punti dati potrebbe non essere un sottospazio di codimensione 1 (anche nel caso bidimensionale).
Le celle di Voronoi possono essere definite anche misurando le distanze di oggetti che non siano punti. Il diagramma di Voronoi di tali celle è anche detto asse mediale. Anche quando gli oggetti sono segmenti, le celle di Voronoi possono avere spigoli non rettilinei. L'asse mediale è utilizzato in decomposizione di immagini, optical character recognition e altre applicazioni computazionali. In scienza dei materiali, le microstrutture policristalline in certe leghe metalliche sono solitamente rappresentate utilizzando tassellazioni di Voronoi. Una versione semplificata del diagramma di Voronoi per segmenti rettilinei non isolati è la struttura che si ottiene incrociando le bisettrici dei loro angoli.
La descrizione del diagramma di Voronoi di $n$ punti in uno spazio $d$-dimensionale richiede spazio $O(n^{\lceil d/2\rceil })$. Ciononostante, i diagrammi di Voronoi sono spesso irrealizzabili per $d>2.$ Un'alternativa è in questi casi l'utilizzo di diagrammi di Voronoi approssimati, in cui le celle di Voronoi hanno contorni sfumati, che possono essere approssimati.

## Condizioni al contorno periodiche

Le condizioni al contorno periodiche sono utilizzate per simulare un sistema infinito replicando periodicamente un sistema finito in tutte le direzioni. Questo approccio aiuta a eliminare gli effetti di contorno senza richiedere una quantità di calcoli eccessivamente elevata. Per creare un diagramma di Voronoi con condizioni al contorno periodiche in un mezzo discreto con elementi di dimensioni $M\times N,$ è sufficiente calcolare le coordinate degli elementi vicini modulo $M$ e $N,$ rispettivamente. In questo modo, gli elementi sul confine destro del reticolo discreto risultano essere adiacenti agli elementi sul confine sinistro e gli elementi sul confine inferiore risultano essere adiacenti agli elementi sul confine superiore. Un esempio di diagramma di Voronoi con condizioni al contorno periodiche è mostrato nella figura a destra. L'animazione dimostra la periodicità del diagramma facendo scorrere l'immagine in orizzontale e in verticale.

## Applicazioni

Si può sfruttare la struttura di un diagramma di Voronoi per scoprire il punto di $S$ più vicino ad un punto dato $x$ senza calcolare ad ogni richiesta la distanza di $x$ da ogni elemento di $S$. Una tale ricerca può avere applicazioni geografiche in sistemi informativi geografici (ad esempio "trova l'ospedale più vicino ad una data abitazione") o nella ricerca di elementi simili in un database.
I diagrammi di Voronoi sono anche utili nella fisica dei polimeri; possono essere infatti utilizzati per rappresentare il volume libero del polimero. Possono essere inoltre utilizzati nello studio delle capacità delle reti wireless.

## Curiosità

Il software di modding mappe di Company of Heroes 2 calcola il territorio influenzato dai punti strategici del gioco mediante un diagramma di Voronoi di variabile complessità, come esemplificato dal comando "Calculate Voronoi", presente nel suddetto devkit.