This is a repost from a question on Computational Science. No proper answer was found and it was suggested that TCS might be able to answer. So here it goes:Is there an algorithm that enumerates the graphs that correspond to some Delaunay tesselation of points in 3D? If so, is there an efficient parameterization of geometries that correspond to any Delaunay graph?More precisely:Let $G_N$ be the set of graphs with $N$ vertices.Let $D: \mathbb{R}^{N\times 3} \to G_N$ be a map of $N$ points in $\mathbb{R}^3$ to a graph corresponding to a Delaunay tesselation of said points in 3D. How do I enumerate $D(\mathbb{R}^{N\times 3})$ (efficiently)?Further, given a graph $g\in D(\mathbb{R}^{N\times 3})$, how can I parameterize $D^{-1}(g)$ (efficiently)?$D$ should be invariant under translations and rotations of $\mathbb{R}^3$, so I'm more interested in the remaining degrees of freedom.For example in 2D, 4 points may generate 2 Delaunay graphs.$$ \begin{matrix}1 & - & 2 & - & 3 \\&\diagdown &| & \diagup\\&&4\end{matrix}\mbox{ and }\begin{matrix}1 & - & 2\\|& \times & |\\3 & - & 4\end{matrix}$$The first of these graphs may be parameterized by any position of points 1, 2 and 4, i.e., $\mathbb{R}^{3\times 3}$, while point 3 would be any point $x_3(r,\theta)=c(x_1,x_2,x_4) + r\left(\begin{array}{c} \cos(\theta) \\ \sin(\theta)\end{array}\right)$ where $r$ is larger than the radius of the circle circumscribing points 1, 2, and 4 centered at $c(x_1,x_2,x_4)$ and $x_i$ is the position of point $i$.
Efficient Enumeration and Parameterization of Graphs Deriving from Delaunay Tesselations in 3D
ds.algorithms;graph theory;cg.comp geom