<p>This is a repost from a <a href="https://scicomp.stackexchange.com/questions/982/enumeration-of-graphs-deriving-from-delaunay-tesselations-in-3d">question on Computational Science</a>. No proper answer was found and it was suggested that TCS might be able to answer. So here it goes:</p>

<p>Is there an algorithm that enumerates the graphs that correspond to some Delaunay tesselation of points in 3D? </p>

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

<p>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. </p>

<p>How do I enumerate $D(\mathbb{R}^{N\times 3})$ (efficiently)?</p>

<p>Further, given a graph $g\in D(\mathbb{R}^{N\times 3})$, how can I parameterize $D^{-1}(g)$ (efficiently)?</p>

<p>$D$ should be invariant under translations and rotations of $\mathbb{R}^3$, so I'm more interested in the remaining degrees of freedom.</p>

<p>For example in 2D, 4 points may generate 2 Delaunay graphs.</p>

<p>$$ \begin{matrix}
1 &amp; - &amp; 2 &amp; - &amp; 3 \\
&amp;\diagdown &amp;| &amp; \diagup\\
&amp;&amp;4
\end{matrix}\mbox{ and }
\begin{matrix}
1 &amp; - &amp; 2\\
|&amp; \times &amp; |\\
3 &amp; - &amp; 4
\end{matrix}$$</p>

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

CC BY-SA 3.0
2012-03-05T03:58:16.050Z
This is a hard problem. We do not know how to solve efficiently easier variants of this problem. And even if we do, the numbers are huge. See for example: http://dl.acm.org/citation.cfm?id=1377733 and http://www.inf.fu-berlin.de/inst/pubs/tr-b-95-20.abstract.html
Sariel Har-Peled
CC BY-SA 3.0
2012-03-05T12:59:58.687Z
@SarielHar-Peled: So the answer to my questions is a resounding "no"? How about approximations?
Deathbreath
CC BY-SA 3.0
2012-03-05T17:02:03.723Z
Its not a no. It is more like an interesting question, and do publish it if you get something interesting. The following paper is also relevant: M. Sharir and A. Sheffer,
Counting triangulations of planar point sets,
Electronic J. Combinat. 18 (2011), P70. Also in arXiv:0911.3352.
Sariel Har-Peled
CC BY-SA 3.0
2012-03-05T17:49:23.480Z
@SarielHar-Peled: Thanks for the references. Since I'm in computational chemistry and not TCS or Math, I doubt I'll put a dent into it. But if I do ...
Deathbreath
CC BY-SA 3.0
2012-02-22T04:31:42.443Z
The four-point examples are incomplete, unless you are excluding degenerate cases.  The Delaunay complex of any four points on a common circle is a single quadrilateral, and the Delaunay complex of any four points on a common line is a path.  (There are even more cases if you allow coincident points.)
Jeffε
CC BY-SA 3.0
2012-02-22T04:45:29.080Z
@JɛﬀE All points are considered to be distinct and in general position. A solution that applies to all possible special cases would definitely be appreciated :)
Deathbreath
<ds.algorithms><graph-theory><cg.comp-geom>
Efficient Enumeration and Parameterization of Graphs Deriving from Delaunay Tesselations in 3D
Deathbreath
# Efficient Enumeration and Parameterization of Graphs Deriving from Delaunay Tesselations in 3D

(Asked by: username_0 on 2012-02-22)

This is a repost from a [question on Computational Science](https://scicomp.stackexchange.com/questions/982/enumeration-of-graphs-deriving-from-delaunay-tesselations-in-3d). 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$.

**Tags:** ds.algorithms, graph-theory, cg.comp-geom
> **Comments:**
> **username_2**: The four-point examples are incomplete, unless you are excluding degenerate cases.  The Delaunay complex of any four points on a common circle is a single quadrilateral, and the Delaunay complex of any four points on a common line is a path.  (There are even more cases if you allow coincident points.)  
> **username_0**: @JɛﬀE All points are considered to be distinct and in general position. A solution that applies to all possible special cases would definitely be appreciated :)  
> **username_1**: This is a hard problem. We do not know how to solve efficiently easier variants of this problem. And even if we do, the numbers are huge. See for example: http://dl.acm.org/citation.cfm?id=1377733 and http://www.inf.fu-berlin.de/inst/pubs/tr-b-95-20.abstract.html  
> **username_0**: @SarielHar-Peled: So the answer to my questions is a resounding "no"? How about approximations?  
> **username_1**: Its not a no. It is more like an interesting question, and do publish it if you get something interesting. The following paper is also relevant: M. Sharir and A. Sheffer, Counting triangulations of planar point sets, Electronic J. Combinat. 18 (2011), P70. Also in arXiv:0911.3352.  
> **username_0**: @SarielHar-Peled: Thanks for the references. Since I'm in computational chemistry and not TCS or Math, I doubt I'll put a dent into it. But if I do ...  

---

## 0 answers

