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

Improve this question
$\endgroup$
11
  • $\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, 2012 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, 2012 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, 2012 at 23:15
  • $\begingroup$ @Szabolcs: I hope the edit clarifies the problem. $\endgroup$
    – Deathbreath
    Feb 14, 2012 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, 2012 at 8:47

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
5
  • $\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, 2012 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, 2012 at 22:01
  • $\begingroup$ Those are interesting references. I'll have my library furnish copies to me. $\endgroup$
    – Deathbreath
    Feb 14, 2012 at 23:22
  • $\begingroup$ It seems these refs are harder to get than anticipated. $\endgroup$
    – Deathbreath
    Feb 18, 2012 at 4:06
  • $\begingroup$ Thank you anyway for the bounty, I hope they are useful when you finally get them. $\endgroup$
    – astrojuanlu
    Feb 21, 2012 at 23:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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