Voronoin diagrammi

**Voronoin diagrammi** on matematiikassa tason jako osiin annetusta erillisten pisteiden joukosta mitattujen etäisyyksien perusteella. Tämä pistejoukko, johon kuuluvia pisteitä sanotaan siemeniksi, kohteiksi tai generaattoreiksi, oletetaan ennalta annetuksi, ja kutakin tällaista kohdetta vastaava alue käsittää ne alkuperäisen tasoalueen pisteet, jotka ovat lähempänä kyseistä kohdetta kuin mitään muuta. Näin muodostettuja alueita sanotaan Voronoin soluiksi. Pistejoukon määrittämä Voronoin diagrammi on sen Delaunayn kolmioinnin duaali.

Voronoin diagrammi on saanut nimensä Georgi Voronoin mukaan. Siitä käytetään myös nimityksiä **Voronoin tessellaatio**, **Voronoin dekompositio**, **Voronoin partitio** tai **Dirichlet’n tessellaatio** (Peter Gustav Lejeune Dirichlet’n mukaan). Voronoin diagrammeilla on käytännöllisiä ja teoreettisia sovelluksia monilla aloilla, pääasiassa tieteessä ja teknologiassa mutta myös kuvataiteissa.  Alueita, joihin Voronoin diagrammi tason jakaa, sanotaan myös **Thiessenin monikulmioiksi**.

## Yksinkertaisin tapaus
Yksinkertaisimmassa tapauksessa, jota esittää edellä oleva kuva, on annettu äärellinen joukko euklidisen tason pisteitä:  {*p*1, ..., *p**n*}. Tässä tapauksessa jokainen kohde *p**k* on vain yksi piste, ja sitä vastaava Voronoin solu *R**k* käsittää ne euklidisen tason pisteet, joiden etäisyys pisteestä *p**k* on pienempi tai yhtä suuri kuin mistään muusta annettuun joukkoon kuuluvasta pisteestä. Jokainen sellainen solu voidaan muodostaa puolitasojen leikkauksena, ja näin ollen kaikki nämä solut ovat muodoltaan kuperia ja ovat joko monikulmioita tai ulottuvat äärettömän kauas. Voronoin diagrammin janat käsittävät kaikki ne tason pisteet, jotka ovat yhtä etäällä kahden lähimmästä kohteesta. Voronoin kärjet eli solmut ovat pisteet, jotka ovat yhtä etäällä kolmesta tai useammasta kohteesta.

## Muodollinen määritelmä
Olkoon  X  metrinen avaruus, jonka etäisyysfunktio on d. Olkoon K joukko indeksejä ja (P_k)_{k \in K} järjestetty joukko ei-tyhjiä osajoukkoja (kohteita) avaruudessa  X. Kohteeseen P_k liittyvä Voronoin solu eli Voronoin alue,  R_k, on niiden X:n pisteiden joukko, joiden etäisyys  P_k ei ole suurempi kuin niiden etäisyys muista kohteista P_j, missä j on mikä tahansa k:sta poikkeava indeksin arvo. Toisin sanoen jos  d(x,\, A) = \inf\{d(x,\, a) \mid a \in A\} merkitsee pisteen x ja osajoukon A välistä etäisyyttä, on

: R_k = \{x \in X \mid d(x, P_k) \leq d(x, P_j)\; \text{kaikilla}\; j \neq k\}

Voronoin diagrammi on yksinkertaisesti solujen (R_k)_{k \in K}  järjestetty joukko. Periaatteessa osa kohteista saattaa olla osittain tai jopa kokonaan päällekkäisiä (kuten jäljempänä olevassa sovelluksessa, jossa kohteet tarkoittavat kauppaliikkeitä), mutta tavallisesti niiden edellytetään olevan toisistaan erillisiä. LIsäksi määritelmä sallii, että kohteiden lukumäärä on ääretön, millä tapauksella on sovelluksia lukujen geometriassa ja kristallografiassa, mutta usein rajoitutaan tarkastelemaan tapauksia, joissa niiden lukumäärä on äärellinen.

Siinä erikoistapauksessa, että avaruus on äärellisulotteinen euklidinen avaruus, jokainen kohde pistemäinen, niiden lukumäärä äärellinen ja ne kaikki erillisiä, Voronoin solut ovat kuperia polytooppeja ja ne voidaan esittää kombinatorisella tavalla käyttämällä niiden kärkiä, tahkoja, kaksiulotteisia sivuja jne. Joskus indusoitua kombinatorista rakennetta sanotaan Voronnoin diagrammiksi. Yleisessä tapauksessa Voronoin solut eivät välttämättä ole kuperia tai edes yhtenäisiä.

Euklidisen avaruuden tapauksessa muodollinen määritelmä voidaan muotoilla uudestaan tavanomaisin termein. Jokainen Voronoin monitahokas R_k liittyy generaattoripisteeseen P_k.
Olkoon X euklidisen avaruuden kaikkien pisteiden joukko. Olkoon 
:P_1 piste, joka generoi Voroinoin alueen R_1, 
:P_2 piste, joka generoi alueen R_2, 
:P_3 piste, joka generoi alueen R_3, 
ja niin edelleen. Silloin jokainen Voronoin monikulmion piste on lähempänä tämän monikulmion generaattoripistettä kuin mitään muuta generaattoripistettä.

## Esimerkki
Yksinkertaisena sovellusesimerkkinä voidaan tarkastella jonkin alan liikkeiden sijaintia kaupungissa. Oletetaan, että on arvioitava asiakkaiden lukumäärä kussakin liikkeessä. Jos liikkeet ovat kaikissa muissa suhteissa samanlaiset, esimerkiksi hintojen, tavaravalikoimien ja palvelun laadun osalta, voidaan olettaa, että yleensä jokainen asiakas käy lähimmässä kaupassa. Tässä tapauksessa voidaan muodostaa Voronoin diagrammi, jonka kohteet ovat nämä kauppaliikkeet. Kuhunkin yksittäiseen liikkeeseen \scriptstyle P_k liittyvä Voronoin solu \scriptstyle R_k voidaan siis käsittää alueeksi, jonka asukkaat käyvät ostoksilla kyseisessä liikkeessä.

Kahden pisteen välinen etäisyys voidaan määritellä eri tavoin. Geometriassa käytetään tavallisesti *euklidista etäisyyttä:
<math>\ell_2 = d\left[\left(a_1, a_2\right), \left(b_1, b_2\right)\right] = \sqrt{\left(a_1 - b_1\right)^2 + \left(a_2 - b_2\right)^2}</math>
joka vastaa paikkojen välistä etäisyyttä linnunteitse. Kaupungissa on kuitenkin usein mielekkäämpää käyttää katuja pitkin mitattuja etäisyyksiä. Jos kaupunki on rakennettu säännöllisen [[ruutukaava]]n mukaan ja kadut ovat koordinaattiakselien suuntaisia, tällöin saadaan niin sanottu [[Manhattan-metriikka]], jossa kahden pisteen välinen etäisyys on :<math>d\left[\left(a_1, a_2\right), \left(b_1, b_2\right)\right] = \left|a_1 - b_1\right| + \left|a_2 - b_2\right|</math>. 
Voronoin diagrammit tulevat varsin eri näköisiksi riippuen siitä, kummalla tavalla etäisyydet määritellään eli kumpaa metriikkaa käytetään.



==Ominaisuuksia ==
* Voronoin diagrammin [[Voronoin diagrammi]] euklidisessa avaruudessa, kun kohteet ovat pistemäisiä, on samojen pisteiden muodostama [[Delaunayn triangulaatio]].
* Generoivista pisteistä kahta lähimpänä toista sijaitsevaa vastaavat Voronoin solut rajoittuvat toisiinsa.
* Jos euklidisella tasolla on annettuna joukko erillisiä pisteitä, kaksi pistettä ovat vielä
* Jos avaruus on [[normiavaruus]] ja etäisyys jokaisesta kohteesta on annettu (esimerkiksi jos kohteet ovat kompakteja joukkoja tai suljettuja palloja), jokainen Voronoin solu voidaan esittää kohteista eri suuntiin liittyvien janojen yhdisteenä.  Tämä ei välttämättä pidä paikkaansa, jos etäisyyttä ei ole annettu.
* Melko yleisillä ehdoilla (avaruus esimerkiksi voi olla ääretönulotteinen [[uniforminen kupera avaruus]] tai kohteita voi olla äärettömän monta) Voronoin solut ovat seuraavassa mielessä vakaita: jos kohteita siirretään jonkin matkaa tai niiden muotoa muutetaan jonkin verran, myös Voronoin soluihin tulee vain pieniä muutoksia.  Tämä ei kuitenkaan edes kaksiulotteisessa avaruudessa pidä kaikissa tapauksissa paikkansa, jos avaruus ei ole uniforminen ja kupera tai jos se ei ole euklidinen.

==Historia ja tutkimus ==
Vähemmän muodollisesti Voronoin diagrammeja käsitteli jo [[René Descartes|Descartes]] vuonna 1644.. [[Johann Peter Gustav Lejeune Dirichlet|Dirichlet]] käytti 2- ja 3-ulotteisia Voronoin diagrammeja apuna tutkiessaan [[neliömuoto]]ja vuonna 1850.
Brittiläinen lääkäri [[John Snow]] käytti Voronoin diagrammia vuonna 1854 havainnollistamaan sitä, että useimmat [[kolera]]epidemian tuona vuonna Lontoossa tappamat ihmiset asuivat lähempänä tartunnan saanutta Broad Steetin pumppukaivoa kuin mitään muuta vesipumppua.

Nykyisen nimensä Voronoin diagrammit saivat venäläisen matemaatikon [[Georgi Voronoi]]n mukaan, joka määritteli *n*-ulotteisen tapauksen ja tutki sitä vuonna 1908. [[Geofysiikka|Geofysiikassa]] ja [[meteorologia]]ssa paikallisesti jakautuneen aineiston, esimerkiksi sademäärämittausten tuulosten analysointiin käytettyjä Voronoin diagrammeja sanotaan Thiessenin monikulmioiksi amerikkalaisen meteorologin [[Alfred H. Thiessen]]in mukaan. [[Tiiviin aineen fysiikka|Tiiviin aineen fysiikassa]] vastaavanlalisia tessellaatioita sanotaan [[Wigner–Seitzin solu]]iksi. Kiteisen aineen [[käänteishila]]n Voronoin soluja sanotaan [[Brillouinin vyöhyke|Brillouinin vyöhykkeiksi]]. [[Lien ryhmä|Lien ryhmien]] yleisissä verkoissa soluja sanotaan yksinkertaisesti [[perusalue]]iksi. Yleisen [[metrinen avaruus|metrisen avaruuden]] tapauksessa soluja sanotaan usein metrisiksi [[perusmonikulmio]]iksi.

Muita nimityksiä tälle käsitteelle tai joillekin sen tärkeille erikoistapauksille ovat: Voronoin monitahokkaat, Voronoin monikulmiot, vaikutusalue(et), Voronoin jako, Voronoin tessellaatio(t) ja Dirichlet'n tessellaatio(t).

==Esimerkkejä==


Kahdessa tai kolmessa ulottuvuudessa säännöllisten hilamaisten pistejoukkojen Voronoin tessellaatioita ovat monet tunnetut kuviot.
* kaksiulotteinen hila johtaa yleensä epäsäännölliseen hunajakennomaiseen [[tessellaatio]]on, jotka muodostuvat yhtä suurista pisteen suhteen symmetrisistä kuusikulmioista. Jos pisteet muodostavat säännöllisen kolmioverkon, Voronoin diagrammi on myös säännöllinen. Jos pisteet muodostavat suorakulmaisen hilan, kuusikulmioiden sijasta Voronoin solut ovat suorakulmioita tai erikoistapauksessa neliöitä. On kuitenkin myös muita pistejoukkoja, joiden generoima Voronoin diagrammi on suorakulmainen ruudokko; esimerkiksi vektorien (1,0) ja (1/2,1/2) määrittämän hilan Voronoin diagrammi on neliöruudukko.
* [[Kuutiollinen hila|Yksinkertaisen kuutiollisen hilan]] Voronoin diagrammit ovat kuutioita.
* [[Heksagonaalinen tiivispakkaus|Heksagonaalisen tiivispakkauksen]] Voronoin solut ovat [[trapetsorombidodekaedri|trapetsorombidodekaedreja]].
* [[Pintakeskinen kuutiollinen hila|Pintakeskisen kuutiollisen hilan]] Voronoin solut ovat [[rombidodekaedri|rombidodekaedreja]].
* [[Tilakeskinen kuutiollinen hila|Tilakeskisen kuutiollisen hilan]] Voronoin solut ovat [[katkaistu oktaedri|katkaistuja oktaedreja.]]

Pistejoukolle (*x*,&nbsp;*y*), missä *x* kuuluu diskreettiin joukkoon *X* ja *y* diskreettiin joukkoon *Y*, saadaan Voronoin diagrammiksi laatat, joissa nämä pisteet eivät välttämättä ole keskipisteinä.

==Korkeamman kertaluvun Voronoin diagrammit ==
Normaali Voronoin solu määritellään niiden pisteiden joukoksi, jotka ovat lähempänä jotakin joukon *S* pistettä kuin mitään muuta saman joukon pistettä. Vastaavasti *n*:*'nnen kertaluvun Voronoin solu*' määritellään niiden pisteiden joukoksi, joihin liittyy *n* kappaletta joukon *S* pisteitä siten, että nämä pisteet ovat *n* lähimpänä sijaistevaa tämän joukon pistettä. Myös korkeamman kertaluvun Voronoin solut täyttävät yhdessä koko tason.

Korkeamman kertaluvun Voronoin diagrammit voidaan generoida rekursiivisesti. Jos (*n*&nbsp;-&nbsp;1):nnen kertaluvun diagrammi tunnetaan, voidaan *n*:nnen kertaluvun diagrammi muodostaa korvaamalla jokainen joukon *X*&nbsp;=&nbsp;{*x*<sub>1</sub>,&nbsp;*x*<sub>2</sub>,&nbsp;...,&nbsp;*x*<sub>*n*-1</sub>} generoima solu joukon *S*&nbsp;-&nbsp;*X* generoimalla Voronoin diagrammilla.

===Kaukaisimpien pisteiden Voronoin diagrammi===

Annetun *n* pisteen joukon (*n*&nbsp;-&nbsp;1):nnen kertaluvun Voronoin diagrammia sanotaan kaukaisimpien pisteiden Voronoin diagrammiksi.

Jos on annettu pistejoukko *S*&nbsp;=&nbsp;{*p*<sub>1</sub>,&nbsp;*p*<sub>2</sub>,&nbsp;...,&nbsp;*p*<sub>*n*</sub>}, kaukaisimpien pisteiden Voronoin diagrammi jakaa tason soluihin, joista kunkin muodostaa se tason alue, josta katsottuna jokin piste *p*<sub>*i*</sub> on kauempana kuin mikään muu joukon *S* piste. Jokaiseen tällaiseen kohteeseen <math>p_i \in S</math> ei välttämättä liity tällaista solua. Kohteeseen *p*<sub>*i*</sub> nimittäin liittyy tällainen solu, jos ja vain jos se on jokin suppeimman sellaisen kuperan monikulmion kärkipisteistä, johon kaikki *S*:n pisteet kuuluvat.

Olkoot H = {*h*<sub>1</sub>,&nbsp;*h*<sub>2</sub>,&nbsp;...,&nbsp;*h*<sub>*k*</sub>} tämän kuperan monikulmion *P* kärkipisteiden joukko. Silloin kaukaisimpien pisteiden Voronoin diagrammi on tason jako *k* soluun, jollainen liittyy kuhunkin *H*:n pisteeseen siten, ett' piste *q* on kohteeseen *h*<sub>*i*</sub> liittyvässä solussa, jos ja vain jos d(*q*, *h*<sub>*i*</sub>) > d(*q*, *p*<sub>*j*</sub>) kaikilla *p*<sub>*j*</sub>&nbsp;?&nbsp;*S*, joille *h*<sub>*i*</sub> ? *p*<sub>*j*</sub>, missä d(*p*, *q*) on pisteiden *p* ja *q* välinen euklidinen etäisyys.

Kaukaisimpien pisteiden Voronoin diagrammin solujen välisillä rajoilla on topologisen [[reaalipuu]]n rakenne äärettömät säteet lehtinään. Jokainen äärellinen puu on [[isomorfia|isomorfinen]] jonkin sellaisen puun kanssa, joka voidaan täten muodostaa kaukaisimpien pisteiden Voronoin diagrammista.

==Yleistyksiä ja muunnelmia ==
Kuten määritelmästäkin voi päätellä, Voronoin solut voidaan vastaavalla tavalla määritellä muissakin kuin euklidisessa metriikassa, esimerkiksi [[Mahalanobisin metriikka|Mahalanobisin]] ja [[Manhattan-metriikka|Manhattan-metriikassa]]. Näissä tapauksissa Voronoin solujen rajat voivat kuitenkin olla monimutkaisempia kuin euklidisessa tapauksessa.


[[Painotettu Voronoin diagrammi]] saadaan, kun suoraviivaiset etäisyydet generaattoripisteistä korvataan näiden etäisyyksien funktioilla, jotka saadaan antamalla kullekin generaattoripisteelle painokerroin, jolla etäisyys kerrotaan tai joka lisätään siihen. Kukin piste kuuluu siihen Voronoin soluun, jota vastaava näin määritelty funktio saa siinä pienimmän arvon. Toisin kuin metrisissä avaruuksissa, tässä tapauksessa osa Voronoin soluista saattaa olla [[tyhjä joukko|tyhjiä joukkoja]]. [[Potenssidiagrammi]] on Voronoin diagrammi, jonka määritellään ympyräjoukon avulla käyttämällä etäisyyden mittana [[pisteen potenssi]]a ympyröiden suhteen; se voidaan käsittää painotetuksi Voronoin diagrammiksi, jossa kunkin ympyrän sädettä käytetään painokertoimena ja lisätään ympyrän keskipisteestä mitatun etäisyyden neliöön.

Useammassa kuin kahdessa ulottuvuudessa Voronoin diagrammit yleensä sangen monimutkaisia eivätkä ne usein edes ole käytännössä toteutettavissa. Vaihtoehtona on käyttää *likimääräisiä Voronoin diagrammeja*, joissa Voronoin solujen väliset rajat ovat sumeita ja voidaan toteuttaa likimääräisesti.

Voronoin diagrammit liittyvät läheisesti muihin geometrisiin struktuureihin kuten esimerkiksi [[mediaaliakseli]]in, jolla on tietoteknisiä sovelluksia muun muassa kuvien segmentoinnissa, [[tekstintunnistus|tekstintunnistuksessa]], sekä [[vyöhykediagrammi|vyöhykediagrammeihin]]. Ne eroavat Voronoin diagrammista siinä, että lähtökohtana olevat kohteet eli generaattorit eivät välttämättä ole pisteitä vaan voivat olla myös janoja tai monikulmioita. Lisäämällä diagrammiin janat, jotka yhdistävät näiden kohteiden lähimmät pisteet toisiinsa, tasoalue voidaan jakaa osiin. Tätä struktuuria voidaan käyttää [[navigaatioverkko]]na kulkureitin löytämiseksi laajan alueen läpi. Navigaatioverkon käsitettä voidaan yleistää niin, että sitä voidaan soveltaa kolmiulotteisiin ympäristöihin kuten lentokenttään tai monikerroksisiin rakennuksiin.

==Sovelluksia==

=== Luonnontieteissä ===

*[[Biologia]]ssa Voronoin diagrammeja käytetään monien biologisten struktuurien kuten [[solu]]jen sekä luiden mikrorakenteen mallintamiseen. Itse asiassa Voronoin tessellaatioita voidaan käyttää geometrisena apuvälineenä niiden fyysisten rajoitusten ymmärtämiseen, jotka ohjaavat [[kudos]]ten muodostumista.
* [[Hydrologia]]ssa Voronoin diagrammeja käytetään alueellisten sademäärien laskemiseen, kun paikalliset sademäärät on mitattu erillisillä havaintopaikoilla. Tässä yhteydessä niitä kutsutaan tavallisesti Thiessenin monikulmioiksi.
*[[Ekologia]]ssa Voronoin diagrammeja käytetään metsän kasvun tutkimiseen, ja niitä voidaan mahdollisesti soveltaa myös laadittaessa ennustemalleja metsäpaloille.
* [[Laskennallinen kemia|Laskennallisessa kemiassa]] molekyylissä olevien atomiydinten mukaan määräytyviä Voronoin soluja käytetään atomien [[osittaisvaraus]]ten laskemiseen. Tämä suoritetaan [[Voronoin deformaatiotiheys]]menetelmällä.



=== Lääketieteessä ===
* [[Lääketieteellinen diagnoosi|Lääketieteellisessä diagnoosissa]] Voronoin diagrammeihin perustuvia lihaskudoksen malleja voidaan käyttää neuromuskulaaristen sairauksien toteamiseen. 
*[[Epidemiologia]]ssa Voronoin diagrammeja voidaan käyttää tartunnan lähteiden jäljittämiseen epidemioiden esiintyessä. Yhtenä ensimmäisistä tällaisen tutkimuksen teki [[John Snow]] vuoden 1854 koleraepidemiasta Lontoon [[Soho]]ssa. Hän osoitti tällä tavoin korrelaation koleratartunnan ja henkilön asuinpaikan välillä, mikä viittasi siihen, että valtaosa tartunnan saaneista ja siihen kuolleista oli saanut juomavetensä eräästä tietystä kaivosta.

=== Insinöörialoilla ===
*[[Polymeeri]]fysiikassa Voronoin diagrammeja voidaan käyttää esittämään polymeerien vapaata tilavuutta.
* [[Materiaalitiede|Materiaalitieteissä]] metalliseosten monikiteistä mikrorakennetta kuvataan usein Voronoin diagrammeilla. [[Kiinteän olomuodon fysiikka|Kiinteän olomuodon fysiikassa]] [[Wigner–Seitzin solu]]t ovat kiteisen aineen Voronoin soluja. Kiteisiin, joiden symmetriaa esittää jokin avaruusryhmä, liittyy aaltovektoreiden muodostama [[käänteishila]], jonka Voronoin soluja ovat [[Brillouinin vyöhyke|Brillouinin vyöhykkeet]].
*[[Ilmailu]]ssa valtamerikarttojen päälle asetetaan Voronoin diagrammit, jotka hätätilanteiden varalta osoittavat, mikä lentokenttä tai varalaskupaikka on lähimpänä lentoreitin kutakin kohtaa.
*[[Arkkitehtuuri]]sa Voronoin mallit ovat muun muassa olleet perustana voittaneelle ehdotukselle Australian [[Gold Coast]]in taidekeskuksen, [[Home of the Arts]]in kehittämiseksi.
*[[Kaupunkisuunnittelu]]ssa Voronoin diagrammeja voidaan soveltaa kaupungin sisäisten tavarankuljetusten kulkureittien optimointiin.
* [[Kaivos]]alalla Voronoin monikulmioita käytetään arvokkaiden mineraalien ja muiden luonnonvarojen varantojen arviointiin. Tällöin paikkoja, joista tutkittavaa ainetta on löydetty, käytetään lähtökohtana Voronoin monikulmioiden muodostamiseen.

=== Geometriassa ===
*Pisteiden sijaintia esittävä tietorakenne voidaan rakentaa Voronoin diagrammin huipulle, jotta sen avulla voidaan vastata lähintä naapuria koskeviin kyselyihin sen selvittämiseksi, mikä tietyn­laisista kohteista on lähimpänä annettua kohtaa. Lähimmän naapurein kyselyillä on useita sovelluksia. Niillä voidaan esimerkiksi selvittää, mikä sairaala sijaitsee lähimpänä tiettyä paikkaa, tai mikä kohteet [[tietokanta|tieto­kannassa]] ovat eniten toistensa kaltaisia. Laaja sovellusalue on [[vektorikvantisointi]], jota paljon käytetään [[tiedonpakkaus|tiedon­pakkauksessa]].
*[[Geometria]]ssa Voronoin diagrammeja voidaan käyttää löytämään pistejoukkoon liittyvä suurin tyhjä ympyrä ja sitä ympäröivä monikulmio. Tätä voidaan soveltaa esimerkiksi etsittäessä uudelle tavaratalolle kaupunki­alueelta sijaintipaikka, jossa se on mahdollisimman kaukana kaikista aikaisemmista.
*Voronoin diagrammia yhdessä kaukaisimman pisteen Voronoin diagrammin kanssa käytetään tehokkaissa algoritmeissa, joilla lasketaan pistejoukon [[pyöreys]]. Voroin lähestymistapa on käyttö­kelpoinen myös arvoitaessa pyöreyttä, kun tietoa haetaan [[koordinaattimittauskone|koordinaatti­mittaus­koneesta]].
, niin että niitä voidaan käyttää verkon generointiin, pisteiden sijainnin selvittämiseen, 

=== Tietojenkäsittelyssä ===
*[[Tietoverkko]]jen suunnittelussa Voronoin diagrammeja voidaan käyttää [[langaton verkko|langattoman verkon]] kapasiteetin arviointiin.
* [[Tietokonegrafiikka|Tietokonegrafiikassa]] Voronoin diagrammeja käytetään muodostamaan kappaleen särkymistä tai murtumista esittävien mallien geometriseen muotoiluun. Niillä voidaan myös proseduraalisesti generoida kuvioita, jotka jäljittelevät elävien olentojen rakennetta.
* Automaattisessa [[robottinavigaatio]]ssa Voronoin diagrammeja käytetään vapaiden kulkureittien löytämiseen. Jos pisteet merkitsevät esteitä, graafin kärjet vastaavat reittejä, jotka ovat kauimpana kaikista esteistä ja joissa törmäyksen vaara on pienin.

=== Paikallishallinnossa ===
Australian [[Victoria (Australia)|Victoriassa]] valtion koulut yleensä ottavat oppilaat siihen alkeis- tai ylemmän asteen kouluun, joka on lähimpänä kunkin oppilaan asuinpaikkaa.  Oppilaat ja heidän vanhempansa voivat nähdä tarkoitusta varten laaditun verkkosovelluksen avulla, mikä on lähin koulu. Sovelluksessa paikallisen kartan päälle on asetettu Voronoin diagrammi, jonka kohteina ovat koulut.

==Algoritmit==

Nykyaikainen [[laskennallinen geometria]] on tuottanut tehokkaita algoritmeja Voronoin diagrammien muodostamiseksi.

Suoria algoritmeja ovat:
* [[Fortunen algoritmi]] on [[Asymptoottinen suoritusaika|O]](*n* log(*n*)) -algoritmi Voronoin diagrammin laatimiseksi annetusta tason pistejoukosta.
* [[Lloydin algoritmi]] ja sen yleistykset [[Linde-Buzo-Grayn algoritmi]]n avulla käyttävät Voronoin tessellaatiota mielivaltaisen moniulotteisessa avaruudessa siten, että ne iteratiivisesti suppenevat kohti erästä Voronoin diagramin erityistä muotoa, jota sanotaan [[sentroidinen Voronoin tessellaatio|sentroidiseksi Voronoin tessellaatioksi]]. Siinä jokainen kohde on samalla solunsa keskipiste.

[[Bowyerin–Watsonin algoritmi]], joka suoritusajaltaan vaihtelee *O*(*n* log(*n*)):sta O(*n* log(*n''2)):een. Se muodostaa ensin Delaunayn kolmioinnin missä tahansa määrässä ulottuvuuksia, minkä jälkeen sen avulla voidaan muodostaa Voronoin diagrammi.

## Katso myös

*Lähimmän naapurin interpolaatio

## Lähteet
* 
* 
* 
* 
* 
* 
* 
* 
* 

### Viitteet

## Aiheesta muualla