# 3D Delaunay Triangulation -> Euclidean Minimum Spanning Tree

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.

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

• Doesn't the Delaunay subdivision include all points, by definition? – VA. Apr 21 '10 at 22:50
• 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? – David Eppstein Apr 21 '10 at 23:10
• Just a thought: your second image looks like it could be the result of running a convex hull algorithm rather than a triangulation. – Martin M. W. Apr 21 '10 at 23:11
• 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. – David Doria Apr 22 '10 at 1:34
• 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. – David Eppstein Apr 22 '10 at 1:44