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



3D Delaunay Triangulation -> Euclidean Minimum Spanning Tree
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


