Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
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

1 Answer 1

up vote 0 down vote accepted

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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