Sphere-based Computation of Delaunay Diagrams on Points from 4d Grids

The Delaunay diagram in d dimensions is the dual of the Voronoi diagram of a set of input sites. If we assume no degeneracies in the input, i.e. no d + 2 sites are co-spherical, then the diagram is a triangulation. Because this assumption is common, and can be enforced by symbolic perturbation, we often forget that Delaunay diagrams need not be triangulations. Input sets chosen from integer grids are common in scientific visualization applications, however, and these often have many degeneracies. Perturbation signifcantly increases the size of the Delaunay and dual Voronoi diagrams - a single 4D cube becomes 16 to 24 simplices, so one dual vertex becomes many. Our result is a sphere-based algorithm for direct, incremental computation of the Delaunay diagram in 4D. For input with many degeneracies, its speed is comparable to our fastest Delaunay triangulation program, yet it computes the exact Delaunay diagram.