Given a set of points in the 2-d plane, find the minimum edge size, L, that would allow the construction of a tree whose edges connect all given points, but no edge exceeds length L.
Here is an algorithm, which I think might work but seems slow:
Pick a random point
find the distance of its nearest neighbour, store the distance, d
your set of covered points, S, now has 2 points in it
find the nearest neighbour point (which is not in S) to any points in S and compute its distance to a point in S, e. Add this new point to S.
d = max(d,e)
repeat steps 4 and 5 until all points have been added to S. now d is the required distance L.
I need help determining if this is correct and if so, the time complexity. Also can the algorithm be made faster (it will be run over a lots of data)?