Voronoin diagrammin sovellukset reitinhaussa - Kaiponen, Samuel (2017)
Reitinhaussa on tavoitteena löytää sopiva reitti paikasta toiseen. Reitinhaulle on sovelluksia monella alalla. Tässä tutkielmassa käsitellään erään laskennallisen geometrian rakenteen, Voronoin diagrammin, käyttöä reitinhaussa. Voronoin diagrammin avulla saadaan löydettyä reittejä, jotka pysyttelevät mahdollisimman kaukana esteistä. Tällainen reitti ei ole pituudeltaan optimaalinen, minkä takia sitä muokataan useissa sovelluksissa lyhyemmäksi säilyttäen kuitenkin tarvittava etäisyys esteisiin. Tutkielmassa esitellään myös sovelluksia, joissa käytetään Voronoin diagrammin eri variaatioita tai yhdistetään se muihin menetelmiin. Lisäksi Voronoin diagrammiin perustuvia reitinhakumenetelmiä vertaillaan muihin reittikarttapohjaisiin menetelmiin.