# Find the minimum edge size, L, that would allow the construction of a tree whose edges connect all given 2-d points, but no edge exceeds length L

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:

1. Pick a random point

2. find the distance of its nearest neighbour, store the distance, d

3. your set of covered points, S, now has 2 points in it

4. 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.

5. d = max(d,e)

6. 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)?

Yes, your algorithm is correct. The correctness can be proven by induction on $$S$$ easily.
Instead of growing by selecting the nearest point to $$S$$, a faster way in general should be just selecting the shortest edge available and including both of its end points. How to select the next shortest edge available? Construct a min-heap of all edges up front. Pop out the top of the heap one by one. Using a counter you can stop once all points are included. The length of the last edge included is the minimum edge size wanted.