WIAS Preprint No. 3041, (2023)
On the computation of high dimensional Voronoi diagrams
Authors
- Heida, Martin
ORCID: 0000-0002-7242-8175
2020 Mathematics Subject Classification
- 65N50 65Y20 68Q25 52-08 52Bxx 52-04
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 merging in a given vertex. 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''.
Download Documents