Diagramma di Voronoi

Da Wikipedia, l'enciclopedia libera.
Il diagramma di Voronoi di un insieme casuale di punti nel piano (tutti i punti sono compresi nell'immagine).

In matematica, un diagramma di Voronoi (dal nome di Georgij Voronoi), anche detto tassellatura di Voronoi, 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 di V(p) siano più vicini a p che ad ogni altro punto in S.

Definizione[modifica | modifica wikitesto]

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 ad 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à[modifica | modifica wikitesto]

  • 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[modifica | modifica wikitesto]

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[modifica | modifica wikitesto]

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[modifica | modifica wikitesto]

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[modifica | modifica wikitesto]

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à[modifica | modifica wikitesto]

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

Voci correlate[modifica | modifica wikitesto]

Note[modifica | modifica wikitesto]

  • 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.
  • 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.
  1. ^ S. Arya, T. Malamatos, and D. M. Mount, [www.cs.ust.hk/faculty/arya/pub/stoc02.pdf Space-Efficient Approximate Voronoi diagrams], Proc. 34th ACM Symp. on Theory of Computing (STOC 2002), pp. 721-730.

Altri progetti[modifica | modifica wikitesto]

Collegamenti esterni[modifica | modifica wikitesto]

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