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, ovvero 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

Una sezione di un diagramma di Voronoi per un insieme casuale di punti in un cubo. Si noti che in generale con questo procedimento non si ottiene un diagramma di Voronoi bidimensionale, nonostante le celle, che sono poliedri convessi, abbiano sezioni a loro volta convesse.

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 davvero 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.

Diagramma di Voronoi approssimato di un insieme di punti. Si osservi i colori sfumati dei confini tra le celle di Voronoi.

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.^[1]

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.

Note

^ S. Arya, T. Malamatos, and D. M. Mount, Space-Efficient Approximate Voronoi diagrams, Proc. 34th ACM Symp. on Theory of Computing (STOC 2002), pp. 721-730.

Bibliografia

(DE) Johann Peter Gustav Lejeune Dirichlet (1850). Über die Reduktion der positiven quadratischen Formen mit drei unbestimmten ganzen Zahlen. Journal für die Reine und Angewandte Mathematik, 40:209-227.
(FR) Georgy Voronoi (1907). Nouvelles applications des paramètres continus à la théorie des formes quadratiques. Journal für die Reine und Angewandte Mathematik, 133:97-178, 1907
Atsuyuki Okabe, Barry Boots, Kokichi Sugihara & Sung Nok Chiu (2000). Spatial Tessellations - Concepts and Applications of Voronoi Diagrams. seconda edizione. John Wiley, 2000, 671 pages ISBN 0-471-98635-6
Franz Aurenhammer (1991). Voronoi Diagrams - A Survey of a Fundamental Geometric Data Structure. ACM Computing Surveys, 23(3):345-405, 1991.
(EN) Adrian Bowyer (1981). Computing Dirichlet tessellations, The Computer Journal 1981 24(2):162-166.
(EN) David F. Watson (1981). Computing the n-dimensional tessellation with application to Voronoi polytopes, The Computer Journal, Heyden & Sons Ltd., Vol 2, Num 24, pp. 167–172.
Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Schwarzkopf, Capitolo 7: Voronoi Diagrams, in Computational Geometry, 2ª ed., Springer-Verlag, 2000, pp. 147-163, ISBN 3-540-65620-0. Comprende una descrizione dell'algoritmo di Fortune's algorithm.

Voci correlate

Algoritmo di Fortune—un algoritmo di complessità O(n log(n)) per generare il diagramma di Voronoi di un insieme di punti nel piano
Algoritmo di Bowyer-Watson—un algoritmo per generare diagrammi di Voronoi in qualsiasi dimensione.
Triangolazione di Delaunay
Geometria computazionale
Algoritmo di Lloyd

Altri progetti

Wikimedia Commons contiene immagini o altri file sul diagramma di Voronoi

Collegamenti esterni

Voronoj, diagramma di, in Enciclopedia della Matematica, Istituto dell'Enciclopedia Italiana, 2013.
(EN) Eric W. Weisstein, Diagramma di Voronoi, su MathWorld, Wolfram Research.
(EN) Denis Howe, Diagramma di Voronoi, in Free On-line Dictionary of Computing. Disponibile con licenza GFDL
(EN) Generatore di diagramma di Voronoi online, su alexbeutel.com.
(EN) Dimostrazione in varie metriche, su nirarebakun.com.
(EN) Componenti architetturali parametrizzati e programmati utilizzando i diagrammi di Voronoi, su m-any.org.
(EN) Algoritmo Quick hull per il calcolo dei diagrammi di Voronoi in 2 o più dimensioni, su qhull.org.
(EN) Applicazioni dei Diagrams di Voronoi: dall'Archeologia alla Zoologia, su ics.uci.edu.
(EN) Diagrammdi di Voronoi nella CGAL, la Libreria di Algoritmi per la Geometria Computazionale
(EN) Sito web di Voronoi: utilizzo dei diagrammi di Voronoi per l'analisi dello spazio, su voronoi.com. URL consultato il 18 dicembre 2007 (archiviato dall'url originale il 5 settembre 2008).
(EN) Discussioni e galleria di immagini riguardo alle tassellature di Voronoi centroidali, su math.psu.edu. URL consultato il 18 dicembre 2007 (archiviato dall'url originale il 16 giugno 2013).
(EN) Metodo di Lloyd's per creare diagrammi di Voronoi centroidali da un insieme di punti generatori, su mrl.nyu.edu. URL consultato il 18 dicembre 2007 (archiviato dall'url originale il 6 settembre 2009).
(EN) Diagrammi di Voronoi in Python, su home.scarlet.be. URL consultato il 18 dicembre 2007 (archiviato dall'url originale il 12 marzo 2008).
(EN) Centro di ricerca sui diagrammi di Voronoi, su voronoi.hanyang.ac.kr.

Controllo di autorità	Thesaurus BNCF 54053 · LCCN (EN) sh88006450 · GND (DE) 4226013-9 · BNF (FR) cb12151119k (data) · J9U (EN, HE) 987007534436805171

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica

[1] S. Arya, T. Malamatos, and D. M. Mount, Space-Efficient Approximate Voronoi diagrams, Proc. 34th ACM Symp. on Theory of Computing (STOC 2002), pp. 721-730.

[1]