Diagramma di Voronoi

Un diagramma di Voronoi divide il piano tra un insieme di punti detti siti: a ogni sito appartiene la regione dei punti che sono almeno tanto vicini a esso quanto a qualsiasi altro sito. L’immagine è una finestra sul piano; l’ombreggiatura dentro una regione serve solo alla visualizzazione. La sonda blu è il centro di un cerchio vuoto che arriva al sito più vicino. Qui puoi spostare i siti e vedere cambiare le regioni vicine, far crescere ogni regione dal suo sito, osservare la triangolazione di Delaunay e distribuire i siti più uniformemente verso una struttura a nido d’ape.

I punti almeno tanto vicini a un sito $p$ quanto a un altro sito $q$ formano un semipiano delimitato dall’asse del segmento $pq$. La regione di $p$ è l’intersezione di questi semipiani, uno per ogni altro sito, ed è quindi convessa. Solo alcuni di questi assi diventano lati. I siti le cui regioni condividono un lato con quella di $p$ sono i suoi vicini; gli altri semipiani contengono già tutta la regione. Il riquadro delimita solo la finestra: una regione si estende all’infinito se e solo se il suo sito si trova sul bordo dell’inviluppo convesso di tutti i siti.

Dove si incontrano tre o più regioni, il vertice è equidistante dai loro siti: è quindi il centro di un cerchio che passa per essi. All’interno del cerchio non c’è alcun sito; se ce ne fosse uno, sarebbe più vicino al vertice e il vertice apparterrebbe alla sua regione. Di solito in un vertice si incontrano esattamente tre regioni. Se ne incontrano quattro quando esattamente quattro siti giacciono su uno stesso cerchio vuoto, come su una griglia quadrata: con siti sparsi a caso non accade quasi mai.

Fai crescere fa crescere da ogni sito un disco alla stessa velocità. Ogni punto viene raggiunto per primo dal sito più vicino, perciò i fronti si incontrano esattamente lungo i lati. La piccola vista mostra la stessa crescita di fianco. Sopra ogni punto pone un’altezza uguale alla distanza dal sito più vicino: la più bassa tra le altezze dei coni $z = |x - s|$ che si innalzano sui siti. Le creste sono i lati e la crescita è acqua che sale. L’ultimo punto sommerso è il più alto del paesaggio nel riquadro, cioè il centro del più grande cerchio vuoto con centro nel riquadro.

Triangolazione unisce due siti quando le loro regioni condividono un lato e aggiunge diagonali tratteggiate dove quattro o più siti condividono un cerchio vuoto, come su una griglia quadrata. A meno che tutti i siti siano allineati, il risultato è la triangolazione di Delaunay. La circonferenza circoscritta di ogni triangolo è quella del cerchio vuoto attorno a un vertice del diagramma.

Uniforma sposta ogni sito nel baricentro della sua regione ritagliata dal riquadro e ricostruisce le regioni, giro dopo giro. È l’algoritmo di Lloyd. Il piccolo grafico mostra la distanza quadratica media di un punto del riquadro dal sito più vicino, divisa per l’area del riquadro per sito. Nessun giro può aumentarla. A siti fissi, la minimizzano le regioni del sito più vicino; a regioni fisse, la minimizzano i baricentri. La linea del nido d’ape è un limite inferiore: il valore per esagoni regolari uguali con i siti al centro. Partendo da siti sparsi, il processo si ferma in uno stato stabile vicino, non in un nido d’ape perfetto. Di solito rimangono pentagoni ed ettagoni affiancati, come dislocazioni in un cristallo.

Il diagramma prende il nome da Georgij Voronoj, che studiò queste suddivisioni in qualsiasi dimensione nel 1908; la triangolazione da Boris Delaunay, che la descrisse nel 1934.