b'\n_START_ARTICLE_\nDiagramma di Voronoi\n_START_PARAGRAPH_\nIn 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) \xc3\xa8 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)._NEWLINE_Nel caso pi\xc3\xb9 semplice e comune, quello del piano, dato un insieme finito di punti S, il diagramma di Voronoi per S \xc3\xa8 la partizione del piano che associa una regione V(p) ad ogni punto  in modo tale che tutti i punti all\'interno del perimetro di V(p) siano pi\xc3\xb9 vicini a p che ad ogni altro punto in S.\n_START_SECTION_\nDefinizione\n_START_PARAGRAPH_\nIn ogni insieme (topologicamente) discreto S di punti in uno spazio euclideo e per quasi ogni punto x, c\'\xc3\xa8 un punto in S che \xc3\xa8 il pi\xc3\xb9 vicino a x. Il "quasi" \xc3\xa8 una precisazione necessaria dato che alcuni punti x possono essere equidistanti da 2 o pi\xc3\xb9 punti di S._NEWLINE_Se S contiene solo due punti, a e b, allora il luogo geometrico dei punti equidistanti da a e b \xc3\xa8 un iperpiano, ovvero un sottospazio affine di codimensione 1. Tale iperpiano sar\xc3\xa0 il confine tra l\'insieme di tutti punti pi\xc3\xb9 vicini ad a che a b e l\'insieme di tutti i punti pi\xc3\xb9 vicini a b che ad a. \xc3\x88 l\'asse del segmento ab._NEWLINE_In generale, l\'insieme dei punti pi\xc3\xb9 vicini ad un punto  che ad ogni altro punto di S \xc3\xa8 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 \xc3\xa8 una tassellatura dell\'intero spazio e viene detta tassellatura di Voronoi corrispondente all\'insieme S. Se la dimensione dello spazio \xc3\xa8 solo 2, \xc3\xa8 facile rappresentare graficamente le tassellazioni di Voronoi; \xc3\xa8 a questo caso che si riferisce solitamente l\'accezione diagramma di Voronoi.\n_START_SECTION_\nStoria\n_START_PARAGRAPH_\nL\'utilizzo informale dei diagrammi di Voronoi pu\xc3\xb2 essere fatto risalire a Cartesio nel 1644. Dirichlet utilizz\xc3\xb2 diagrammi di Voronoi bidimensionali e tridimensionali nei suoi studi delle forme quadratiche, nel 1850. Il medico britannico John Snow utilizz\xc3\xb2 un diagramma di Voronoi nel 1854 per illustrare come la maggioranza delle persone morte nell\'epidemia di colera a Soho viveva pi\xc3\xb9 vicino ad una delle pompe infette di Broad Street che ad ogni altra pompa d\'acqua._NEWLINE_I diagrammi di Voronoi traggono il loro nome dal matematico russo Georgii Fedoseevich Voronoi che defin\xc3\xac e studi\xc3\xb2 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\xc3\xa0 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.\n_START_SECTION_\nGeneralizzazioni\n_START_PARAGRAPH_\nLe 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 \xc3\xa8 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)._NEWLINE_Le celle di Voronoi possono essere definite anche misurando le distanze di oggetti che non siano punti. Il diagramma di Voronoi di tali celle \xc3\xa8 anche detto asse mediale. Anche quando gli oggetti sono segmenti, le celle di Voronoi possono avere spigoli non rettilinei. L\'asse mediale \xc3\xa8 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 \xc3\xa8 la struttura che si ottiene incrociando le bisettrici dei loro angoli._NEWLINE_La descrizione del diagramma di Voronoi di n punti in uno spazio d-dimensionale richiede spazio . Ciononostante, i diagrammi di Voronoi sono spesso irrealizzabili per d>2. Un\'alternativa \xc3\xa8 in questi casi l\'utilizzo di diagrammi di Voronoi approssimati, in cui le celle di Voronoi hanno contorni sfumati, che possono essere approssimati.\n_START_SECTION_\nApplicazioni\n_START_PARAGRAPH_\nSi pu\xc3\xb2 sfruttare la struttura di un diagramma di Voronoi per scoprire il punto di S pi\xc3\xb9 vicino ad un punto dato x senza calcolare ad ogni richiesta la distanza di x da ogni elemento di S. Una tale ricerca pu\xc3\xb2 avere applicazioni geografiche in sistemi informativi geografici (ad esempio "trova l\'ospedale pi\xc3\xb9 vicino ad una data abitazione") o nella ricerca di elementi simili in un database._NEWLINE_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\xc3\xa0 delle reti wireless.\n_START_SECTION_\nCuriosit\xc3\xa0\n_START_PARAGRAPH_\n-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\xc3\xa0, come esemplificato dal comando "Calculate Voronoi", presente nel suddetto devkit.'