1
$\begingroup$

I read that the Euclidean Minimum Spanning Tree (EMST) of a set of points is a subgraph of any Delaunay triangulation. Apparently the easiest/fastest way to obtain the EMST is to find the Deluanay triangulation and then run Prim's algorithm on the resulting edges. However, I have a set of 3D points, and the Delaunay triangulation doesn't include many of the "interior" points.

Here are my points: http://rpi.edu/~doriad/bunny.jpg

And here are the edges of the tetrahedra that are produced by the Delaunay triangulation: http://rpi.edu/~doriad/bunnyDelaunay.jpg

You can see that many of the points are not vertices of any of the tetrahedra. How, then, would finding the MST of these edges produce the EMST on the points, since the EMST must go through ALL of the points?

Thanks in advance for any help,

Dave

$\endgroup$
6
  • $\begingroup$ Doesn't the Delaunay subdivision include all points, by definition? $\endgroup$
    – VA.
    Apr 21, 2010 at 22:50
  • $\begingroup$ It appears that you do NOT have the 3d Delaunay triangulation. What you have is the convex hull. In any case, Delaunay triangulation is not especially efficient for EMST in three dimensions, since it may be a complete graph, and if you're going to form a complete graph anyway then why not just use that and avoid the difficulty of finding the Delaunay triangulation? $\endgroup$ Apr 21, 2010 at 23:10
  • $\begingroup$ Just a thought: your second image looks like it could be the result of running a convex hull algorithm rather than a triangulation. $\endgroup$ Apr 21, 2010 at 23:11
  • $\begingroup$ Ok, I have inquired why the Delaunay3D algorithm I am using does not seem to actually be producing the appropriate triangulation. David Eppstein - Do you have a better recommendation for EMST in 3D? I tried to make a complete graph on 300,000 points... that didn't go so well hahaha. $\endgroup$ Apr 22, 2010 at 1:34
  • $\begingroup$ The best theoretical time bounds for 3d EMST are I think O((n log n)^{4/3}) — see dx.doi.org/10.1007/BF02574698 — but I doubt that's a practical algorithm. $\endgroup$ Apr 22, 2010 at 1:44

1 Answer 1

0
$\begingroup$

Sorry for the confusion - the "wireframe" view of the tetrahedralization of the points was only showing the outside surface (convex hull). Of course all of your comments are correct - the Delaunay triangulation indeed includes ALL points. Then the EMST is a subgraph of it.

All is well - thanks for the confirmations.

Dave

$\endgroup$

Your Answer

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

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