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 kolmionnin duaali.
Voronoin diagrammi on saanut nimensä Georgy 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 monikumioiksi.

Yksinkertaisin tapaus

Yksinkertaisimmassa tapauksessa, jota esittää edellä oleva kuva, on annettu äärellinen joukko euklidisen tason pisteitä:  {p₁, ..., pₙ}. Tässä tapauksessa jokainen kohde pₖ on vain yksi piste, ja sitä vastaava Voronoin solu Rₖ käsittää ne euklidisen tason pisteet, joiden etäisyys pisteestä pₖ 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.

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  liittyvä Voronoin solu  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ä:
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 ruutukaavan mukaan ja kadut ovat koordinaattiakselien suuntaisia, tällöin saadaan niin sanottu Manhattan-metriikka, jossa kahden pisteen välinen etäisyys on :. 
Voronoin diagrammit tulevat varsin eri näköisiksi riippuen siitä, kummalla tavalla etäisyydet määritellään eli kumpaa metriikkaa käytetään.

Historia ja tutkimus

Vähemmän muodollisesti Voronoin diagrammeja käsitteli jo Descartes vuonna 1644. Dirichlet käytti 2- ja 3-ulotteisia Voronoin diagrammeja apuna tutkiessaan neliömuotoja vuonna 1850.
Brittiläinen lääkäri John Snow käytti Voronoin diagramia vuonna 1854 havainnollistamaan sitä, että useimmat koleraepidemian 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 matemaatikko Georgy Voronoyn mukaan, joka määritteli n-ulotteisen tapauksen ja tutki sitä vuonna 1908. Geofysiikassa ja meteorologiasa paikallisesti jakautuneen aineiston, esimerkisi sademäärämittausten tuulosten analysointiin käytettyjä Voronoin diagrammeja sanotaan Thiesseni monikulmiosi amerikkalisen meteorologi Alfred H. Thiessenin mukaan. Tiiviin aineen fysiikassa vastaavanlalisia tessellaatioita sanotaan Wigner–Seitzin soluiksi. Kiteisen aineen käänteishilan Voronoin soluja sanotaan Brillouinin vyöhykkeiksi. Lien ryhmien yleisissä verkoissa soluja sanotaan yksinkertaisesti perusalueiksi. Yleisen metrisen avaruuden tapauksessa soluja sanotaan usein metrisiksi perusmonikulmioiksi.
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).

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 - 1):nnen kertaluvun diagrammi tunnetaan, voidaan n:nnen kertaluvun diagrammi muodostaa korvaamalla jokainen joukon X = {x₁, x₂, ..., xₙ₋₁} generoima solu joukon S - X generoimalla Voronoin diagrammilla.

Kaukaisimpien pisteiden Voronoin diagrammi

Annetun n pisteen joukon (n - 1):nnen kertaluvun Voronoin diagrammia sanotaan kaukaisimpien pisteiden Voronoin diagrammiksi.
Jos on annettu pistejoukko S = {p₁, p₂, ..., pₙ}, kaukaisimpien pisteiden Voronoin diagrammi jakaa tason soluihin, joista kunkin muodostaa se tason alue, josta katsottuna jokin piste pᵢ on kauempana kuin mikään muu joukon S piste. Jokaiseen tällaiseen kohteeseen  ei välttämättä liity tällaista solua. Kohteeseen pᵢ 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₁, h₂, ..., hₖ} 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ᵢ liittyvässä solussa, jos ja vain jos d(q, hᵢ) > d(q, pⱼ) kaikilla pⱼ ? S, joille hᵢ ? pⱼ, missä d(p, q) on pisteiden p ja q välinen euklidinen etäisyys.
Kaukaisimpien pisteiden Voronoin diagrammin soluen välisillä rajoilla on topologisen reaalipuun rakenne äärettömät säteet lehtinään. Jokainen äärellinen puu on isomorfinen jonkin sellaisen puun kanssa, joka voidaan täten muodostaa kaukaisimpen 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 ja 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 tyhjiä joukkoja. Potenssidiagrammi on Voronoin diagrammi, jonka määritellään ympyräjoukon avulla käyttämällä etäisyyden mittana pisteen potenssia 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 mediaaliakseliin, jolla on tietoteknisiä sovelluksia muun muassa kuvien segmentoinnissa, tekstintunnistuksessa, sekä 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ää navigaatioverkkona 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.

Paikallishallinnossa

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