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

allpoints, by definition? $\endgroup$ – VA. Apr 21 '10 at 22:501more comment