Diagramma di Voronoi: differenze tra le versioni

 

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 [[Johann Peter Gustav Lejeune Dirichlet|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 [[punto (geometria)|punti]]).

 

== Esempi ==

 

Molte tassellazioni di Voronoi di griglie regolari di punti in due o tre dimensioni risultano essere tassellazioni familiari:

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 <math>O(n^{\lceil d/2 \rceil})</math>. 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.<ref>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.</ref>