# Enumeration of graphs deriving from Delaunay tessellations in 3D

Is there an algorithm that enumerates the graphs that correspond to some Delaunay tessellation of points in 3D?

If so, is there an efficient parameterization of geometries that correspond to any "Delaunay graph"?

I am looking to enumerate systematically all stable geometries of molecules of a specified composition without any a priori knowledge of bonding etc.

EDIT: Let $G_N$ be the set of graphs with $N$ vertices. Let $D: \mathbb{R}^{3N} \to G_N$ be a map of $N$ points in $\mathbb{R}^3$ to a graph corresponding to a Delaunay tessellation of said points in 3D.

How do I enumerate $D(\mathbb{R}^{3N})$ (efficiently)?

Further, given a graph $g\in G_n$, how can I parameterize $D^{-1}(g)$ (efficiently)?

EDIT: Example in 2D: For 4 points there are 2 Delaunay graphs. $$\begin{matrix} 1 & - & 2 & - & 3 \\ &\diagdown &| & \diagup\\ &&4 \end{matrix}\mbox{ and } \begin{matrix} 1 & - & 2\\ |& \times & |\\ 3 & - & 4 \end{matrix}$$

Or shown in an explicitly planar way: 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$.

• What do you mean by "efficient parameterization of geometries". Also I'm not a chemist so what does "stable geometries of molecules of a specified composition" mean? With a bit more clarification this may be easily answerable. – Gareth A. Lloyd Jan 30 '12 at 10:04
• For $N$ points in general position in 3D, there are $3N-6$ independent degrees of freedom ($3N-3$ for the center of mass and another 3 degrees for the principal axes of rotation). Each such set has some Delaunay tesselation. I would like to invert this process: given a Delaunay tesselation, I want a parameterization of all sets of $N$ points that would lead to this Delaunay tesselation. A stable geometry is a set of $N$ points in space with associated positive weights for which the energy functional is locally minimal. – Deathbreath Jan 30 '12 at 18:27
• Are you asking to find all possible Delaunay triangulations? Can you clarify a bit? You set a bounty on this, but I have a feeling the question is still not clear to many. – Szabolcs Feb 14 '12 at 23:15
• @Szabolcs: I hope the edit clarifies the problem. – Deathbreath Feb 14 '12 at 23:32
• @Deathbreath a little bit ... do I understand it right that you need to find all graphs that could correspond to a Delaunay triangulation of some set of $N$ points in 3D? Can you give a specific example? For example, in 2D for 4 points, are the graphs you need $(12, 23, 31, 24, 43)$ and $(12, 23, 31, 14, 24, 34)$ (ignoring collinear points)? (The digits represent vertices and the digit pairs edges in my notation.) – Szabolcs Feb 15 '12 at 8:47

[...] for each $R_i$ of a Voronoi diagram, the set of points in $R_i$ contained in some generating set $P$ is either a singleton or the interior of a polyhedron.
• There are only $3N-6$ DoF of relevance ($3N-5$ if the points are on a line) as either tesselation (Voronoi or Delaunay) is translationally and rotationally invariant. I meant Delaunay tetrahedration (or more generally tesselation). The map $D: \mathbb{R}^{3N} \to G_N$, where $G_N$ is the set of graphs with $N$ vertices, which maps a set of $N$ points in 3D to the graph corresponding to the Delaunay tesselation has a theoretical inverse $D^{-1}: G_N\to P(\mathbb{R}^{3N-6})$. I take it your answer is: a) $D(\mathbb{R}^N)$ is not efficiently computable, b) and neither is $D^{-1}(g)$ ($g\in G_N$)? – Deathbreath Feb 14 '12 at 18:13