Evaluating a d-dimensional Voronoi diagram algorithm and its applicability for linear interpolation

Abstract

The Voronoi diagram (or graph) and Delaunay triangulation (or tessellation) are important geometric structures for space partitioning. The former is widely used in many fields as it generates patterns containing useful information on the intrinsic structure of the data. The latter generates a simplicial complex of $d$-simplices, which enables piecewise linear interpolation of scattered data. A simplex is the generalization of a triangle (2-simplex) to any dimension, for example, a three-dimensional simplex is a tetrahedron. Additionally, both structures are dual graphs of each other. This implies that by computing one, the other is also obtained during the process. In lower dimensions, it is possible to generate each structure efficiently by many popular algorithms, but in higher dimensions it becomes increasingly more infeasible as a $d$-dimensional Voronoi diagram can have $\mathcal{O}(n^{\lceil{\frac{d}{2}\rceil}})$ vertices and a $d$-dimensional Delaunay triangulation can have $\mathcal{O}(n^{\lceil{\frac{d}{2}\rceil}})$ simplices, which entails an alternative approach. The Voronoi graph traversal algorithm proposed by \cite{VGT} in 2020 as a solution for computing $d$-dimensional Voronoi diagrams by incremental and stochastic exploration. In this thesis, the Voronoi graph traversal algorithm is surveyed and analyzed with regards to high-dimensional data. Later, components of the algorithm repurposed for piecewise linear interpolation in $d$-dimensions, which is also examined. The interpolation method searches for the simplex by performing numerous random walks to traverse the Voronoi diagram starting from a Voronoi generator point that is as close as possible to the given query point. When a simplex is found, the values located at its vertices can then be used to estimate the value of the query point. This new method can be applied to machine learning, and it resembles nearest neighbor (KNN) and radial basis function interpolation methods. It was found that the algorithm performed best in contrast to Qhull (a popular algorithm for generating these structures in any dimension) in extremely high dimensions $d > 10$, where computing and exploring a subset of vertices becomes the more practical approach. Conversely, piecewise linear interpolation performed best in dimensions between 2 and 8 since it became gradually more challenging to find simplices in $d > 8$ due to the random nature of the algorithm.

Voronoi-diagrammi ja Delaunay-kolmiointi (tai tessellaatio) ovat tärkeitä geometrisia rakenteita avaruuden osioinnissa. Voronoi-diagrammia on hyödynnetty laajasti eri aloilla, sillä sen muodostamat alueet sisältävät hyödyllistä tietoa datan rakenteesta. Delaunay-kolmiointi tuottaa kompleksin, joka koostuu toisiinsa liitetyistä $d$-simplekseistä, jotka mahdollistavat paloittain lineaarisen interpolaation. Simpleksi on kolmion (2-simpleksin) yleistys mihin tahansa ulottuvuuteen, esimerkiksi kolmilotteinen simpleksi on tetraedri. Lisäksi molemmat rakenteet ovat toistensa geometrisia duaaleja. Tämä tarkoittaa, että laskemalla jompikumpi on mahdollista saada myös samalla toinen laskentaprosessin aikana. Matalissa dimensioissa on mahdollista generoida molemmat rakenteet tehokkaasti monilla yleisillä algoritmeilla, mutta korkeissa dimensioissa tästä tulee entistä hankalampaa, sillä $d$-dimensisellä Voronoin-diagrammissa voi olla $\mathcal{O}(n^{\lceil{\frac{d}{2}\rceil}})$ solmua ja $d$-dimensisellä Delaunayn-kolmioinnissa voi olla $\mathcal{O}(n^{\lceil{\frac{d}{2}\rceil}})$ simpleksejä, mikä edellyttää vaihtoehtoista lähestymistapaa. Vuonna 2020 julkaistussa lähteessä \cite{VGT} on esitetty algoritmi, jolla voidaan generoida $d$-ulotteisia Voronoin-diagrammeja hyödyntämällä stokastista prosessia rakenteen vaiheittaiseen tutkimiseen. Tässä tutkielmassa tarkastellaan ja analysoidaan tätä algoritmia korkeadimensioisen datan osalta. Myöhemmin tarkastellaan myös algoritmin osia, jotka on uudelleenkäytetty paloittain lineaariseen interpolointiin $d$-dimensioissa. Interpolointimenetelmä etsii simpleksin suorittamalla useita satunnaiskulkuja Voronoi-diagrammin läpikäymiseksi Voronoi-generaattorin pisteestä, joka on mahdollisimman lähellä annettua pistettä, jonka arvoa halutaan selvittää. Kun simpleksi on löydetty, sen kärkipisteissä sijaitsevia arvoja voidaan käyttää annetun pisteen interpolointiin. Kyseistä uutta menetelmää voidaan soveltaa koneoppimiseen, ja se muistuttaa lähimmän naapurin ja radiaalisen interpoloinnin menetelmiä. On havaittu, että algoritmi toimi parhaiten Qhull:in (suosittu algoritmi näiden rakenteiden generointiin missä tahansa dimensiossa) verrattuna erittäin korkeissa dimensioissa $d > 10$, jolloin solmujen osajoukon laskeminen ja tutkiminen on käytännöllisempi lähestymistapa. Vastaavasti paloittain lineaarinen interpolointi suoriutui parhaiten 2 - 8 dimension välillä, sillä algoritmin satunnaisuuden seurauksena simpleksien etsiminen vaikeutui dimensioissa $d > 8$.