On the computation of high dimensional Voronoi diagrams

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''.