1
$\begingroup$

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

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
0
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Of course, the min-heap should be a balanced tree. $\endgroup$
    – John L.
    Dec 19, 2018 at 22:00
  • $\begingroup$ When the number of nodes are really large, it should be possible to speed up the algorithm by dividing the area that contains all the points into grid. Only edges between points in the same or nearby cells will need to be computed. However, this idea is easily said than done because of its complexity and exceptional cases. $\endgroup$
    – John L.
    Dec 20, 2018 at 6:10
  • $\begingroup$ What about this?: The problem statement is equivalent to finding the minimum L such that for all pairs of points (p,q) we may construct a path of points p_1, …, p_n such that p_1 = p and p_n = q and dist(p_(i+1), p_i )<L for all i. Finding L is equivalent to finding the minimum parameter epsilon in the DSCAN clustering algorithm, run with minPts = 2 so that all points are core points, such that all points are grouped in only 1 cluster. For reference, the DBSCAN algorithm is described here (the important definitions under 'Preliminary') : en.wikipedia.org/wiki/DBSCAN $\endgroup$
    – notbaitatall
    Dec 20, 2018 at 16:59
  • $\begingroup$ By the way, the problem here is, namely, finding the maximum edge-weight of the minimum bottleneck spanning tree for planar points. $\endgroup$
    – John L.
    Dec 20, 2018 at 18:16
  • $\begingroup$ I said 'such that all points are grouped in only 1 cluster.', but I realise the ambiguity of that choice of wording. Apologies. Do you think this new algorithm using DBSCAN is valid? $\endgroup$
    – notbaitatall
    Dec 20, 2018 at 20:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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