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 formula_1 metrinen avaruus, jonka etäisyysfunktio on formula_2. Olkoon formula_3 joukko indeksejä ja formula_4 järjestetty joukko ei-tyhjiä osajoukkoja (kohteita) avaruudessa formula_5. Kohteeseen formula_6 liittyvä Voronoin solu eli Voronoin alue, formula_7, on niiden formula_8:n pisteiden joukko, joiden etäisyys formula_9 ei ole suurempi kuin niiden etäisyys muista kohteista formula_10, missä formula_11 on mikä tahansa formula_12:sta poikkeava indeksin arvo. Toisin sanoen jos formula_13 merkitsee pisteen formula_14 ja osajoukon formula_15 välistä etäisyyttä, on
formula_16
Voronoin diagrammi on yksinkertaisesti solujen formula_17 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 formula_18 liittyy generaattoripisteeseen formula_6.
Olkoon formula_8 euklidisen avaruuden kaikkien pisteiden joukko. Olkoon 
formula_21 piste, joka generoi Voroinoin alueen formula_22, 
formula_23 piste, joka generoi alueen formula_24, 
formula_25 piste, joka generoi alueen formula_26, 
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 formula_27 liittyvä Voronoin solu formula_28 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ä:
formula_29
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 :formula_30. 
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 diagrammia 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 matemaatikon Georgi Voronoin mukaan, joka määritteli "n"-ulotteisen tapauksen ja tutki sitä vuonna 1908. Geofysiikassa ja meteorologiassa paikallisesti jakautuneen aineiston, esimerkiksi sademäärämittausten tuulosten analysointiin käytettyjä Voronoin diagrammeja sanotaan Thiessenin monikulmioiksi amerikkalaisen meteorologin 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).
Esimerkkejä.
Kahdessa tai kolmessa ulottuvuudessa säännöllisten hilamaisten pistejoukkojen Voronoin tessellaatioita ovat monet tunnetut kuviot.
Pistejoukolle ("x", "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" - 1):nnen kertaluvun diagrammi tunnetaan, voidaan "n":nnen kertaluvun diagrammi muodostaa korvaamalla jokainen joukon "X" = {"x"1, "x"2, ..., "x""n"-1} 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"1, "p"2, ..., "p""n"}, kaukaisimpien pisteiden Voronoin diagrammi jakaa tason soluihin, joista kunkin muodostaa se tason alue, josta katsottuna jokin piste "p""i" on kauempana kuin mikään muu joukon "S" piste. Jokaiseen tällaiseen kohteeseen formula_31 ei välttämättä liity tällaista solua. Kohteeseen "p""i" 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"1, "h"2, ..., "h""k"} 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""i" liittyvässä solussa, jos ja vain jos d("q", "h""i") &gt; d("q", "p""j") kaikilla "p""j" ? "S", joille "h""i" ? "p""j", missä d("p", "q") on pisteiden "p" ja "q" välinen euklidinen etäisyys.
Kaukaisimpien pisteiden Voronoin diagrammin solujen 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 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 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.
Sovelluksia.
Geometriassa.
, niin että niitä voidaan käyttää verkon generointiin, pisteiden sijainnin selvittämiseen, 
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.
Algoritmit.
Nykyaikainen laskennallinen geometria on tuottanut tehokkaita algoritmeja Voronoin diagrammien muodostamiseksi.
Suoria algoritmeja ovat:
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.