8
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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.) $\endgroup$ – Jeffε Feb 22 '12 at 4:31
  • $\begingroup$ @JɛffE All points are considered to be distinct and in general position. A solution that applies to all possible special cases would definitely be appreciated :) $\endgroup$ – Deathbreath Feb 22 '12 at 4:45
  • $\begingroup$ 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: dl.acm.org/citation.cfm?id=1377733 and inf.fu-berlin.de/inst/pubs/tr-b-95-20.abstract.html $\endgroup$ – Sariel Har-Peled Mar 5 '12 at 3:58
  • $\begingroup$ @SarielHar-Peled: So the answer to my questions is a resounding "no"? How about approximations? $\endgroup$ – Deathbreath Mar 5 '12 at 12:59
  • $\begingroup$ 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. $\endgroup$ – Sariel Har-Peled Mar 5 '12 at 17:02

Your Answer

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

Browse other questions tagged or ask your own question.