Minimum Spanning Tree on a Grid of Points

I want to find the minimum spanning tree of a grid of n*n points.
And an n*m grid.

While finding minimum spanning trees in the general case is NP complete, I
suspect that in this simplified case, it's easier.

Can anybody point me towards a nice (ie. polynomial time) way to do this?
And how about a Steiner tree?

Thanks for any help,

Alun Harford


.

Quantcast