Sunday, 4 May 2014

graph theory - 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.



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

No comments:

Post a Comment