On the parallelized efficient computation of high dimensional Voronoi diagrams on bounded, unbounded, spherical and periodic domains

Abstract

We investigate a recently implemented new algorithm for the computation of a Voronoi diagram in high dimensions and generalize it to N nodes in general or non-general position using a geometric characterization of edges and vertices. The algorithm consist of local computations, is well suited for parallelization and can be applied to the Euclidean geometry or on the sphere. We provide a mathematical proof that the algorithm is exact, convergent and has computational costs of O(E NN (N))$, where E is the number of edges and NN (N) is the computational cost to calculate the nearest neighbor among N points. We also provide data from performance tests in the recently developed Julia package „HighVoronoi.jl” and compare it to the quickhull algorithm. It turns out that the new approach is particularly well suited for bounded domains, periodic domains and parallelization of computations.