Diagramma di Voronoi: differenze tra le versioni

[[ImmagineFile:Coloured Voronoi 2D.png|right|thumb|222px|Il diagramma di Voronoi di un insieme casuale di punti nel piano (tutti i punti sono compresi nell'immagine).]]

== Definizione ==

In ogni insieme ([[topologia|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''-

In generale, l'insieme dei punti più vicini ad un punto <math>c \in S</math> 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 ''Voronoi diagrams''.

== Proprietà ==

== Storia ==

I diagrammi di Voronoi traggono il loro nome dal matematico russo [[Georgii Voronoi|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 [[cella di Wigner-Seitz|celle di Wigner-Seitz]]. Le tassellazioni di Voronoi del [[reticolo reciproco]] delle [[quantità di moto]] sono dette [[zone di Brillouin]]. Per reticoli generali nei [[gruppo di Lie|gruppi di Lie]], le celle sono semplicemente dette [[dominio fondamentale|domini fondamentali]]. In spazi metrici generici, le celle sono spesso dette [[poligono fondamentale|poligoni fondamentali]].

[[ImmagineFile:Coloured Voronoi 3D slice.png|right|thumb|333px|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.]]

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''<!-- si dirà così davvero? -->. 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.

[[ImmagineFile:ApproximateVoronoiDiagram.svg|right|thumb|200px|Diagramma di Voronoi approssimato di un insieme di punti. Si osservi i colori sfumati dei confini tra le celle di Voronoi.]]

== 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 [[Sistema_informativo_geograficoSistema informativo geografico|sistemi informativi geografici]] (ad esempio "trova l'ospedale più vicino ad una data abitazione") o nella ricerca di elementi simili in un [[database]].

== Note ==

* Franz Aurenhammer (1991). ''Voronoi Diagrams - A Survey of a Fundamental Geometric Data Structure''. ACM Computing Surveys, 23(3):345-405, 1991.

== Collegamenti esterni ==