Comparing Data Structures Used in Divide-and-Conquer Three-Dimensional Voronoi Diagrams

Voronoi diagrams are used in a wide range of applications, and many of those applications are in three dimensional space. Two important benchmarks you can measure for Voronoi solver algorithms are run time and memory usage. Run time is important due to the potential costs of computation, and memory usage allows for larger areas to be analyzed. Run time can be addressed via parallelization, but memory usage is dependent on data structure. In this paper we compare the run time and memory usage of a previously published 3D Voronoi solver implementation that utilized an array data structure with a new novel implementation that utilizes an oct-tree data structure.