On the parallelized efficient computation of high dimensional Voronoi diagrams on bounded, unbounded, spherical and periodic domains
Authors
- Heida, Martin
ORCID: 0000-0002-7242-8175
2020 Mathematics Subject Classification
- 65D18 65Y20 68Q25 52C45 68W10 52C22
Keywords
- Raycast, mesh generation, geometry, HighVoronoi
DOI
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.
Download Documents