12
$\begingroup$

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:

2D delaunay graphs for 4 points

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Gareth A. Lloyd Jan 30 '12 at 10:04
  • $\begingroup$ 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. $\endgroup$ – Deathbreath Jan 30 '12 at 18:27
  • $\begingroup$ 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. $\endgroup$ – Szabolcs Feb 14 '12 at 23:15
  • $\begingroup$ @Szabolcs: I hope the edit clarifies the problem. $\endgroup$ – Deathbreath Feb 14 '12 at 23:32
  • $\begingroup$ @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.) $\endgroup$ – Szabolcs Feb 15 '12 at 8:47
4
+50
$\begingroup$

In Hartvigsen, D.: Recognizing Voronoi Diagrams with Linear Programming several algorithms based on linear programming for recognizing Voronoi tesellations are presented, and states that

[...] 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.

It seems that the topic of the existence and uniqueness of solution to the inverse Voronoi problem is also developed in Winter, L. G.: The inverse problem to the Voronoi diagram.

$\endgroup$
  • $\begingroup$ 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$)? $\endgroup$ – Deathbreath Feb 14 '12 at 18:13
  • $\begingroup$ After understanding your concerns and doing some research, I have found some potentially useful resources. Note though that I can read the full-text version of none of them. $\endgroup$ – astrojuanlu Feb 14 '12 at 22:01
  • $\begingroup$ Those are interesting references. I'll have my library furnish copies to me. $\endgroup$ – Deathbreath Feb 14 '12 at 23:22
  • $\begingroup$ It seems these refs are harder to get than anticipated. $\endgroup$ – Deathbreath Feb 18 '12 at 4:06
  • $\begingroup$ Thank you anyway for the bounty, I hope they are useful when you finally get them. $\endgroup$ – astrojuanlu Feb 21 '12 at 23:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.