I have been given a task where I have to connects all the points in the 2D plane. There are four conditions to to be met:
- Length of the all segments joined together has to be minimal.
- One point can be a part of only one line segment.
- Line segments cannot intersect
- All points have to be used(one can't be left alone but only if it cannot be avoided)
Image to visualize the problem:
The wrong image connected points correctly, although the total length is bigger that the the one in on the left.
At first I thought about sorting the points and doing it with a sweeping line and building a tree of all possibilities, although it does seem like a way to complicated solution with huge complexity. Therefore I search better approaches. I would appreciate some hints what to do, or how could I approach the problem.
k = n/2
?n
being the number of points. Running k-means on your example seemed to produce the correct result every time I tried it. Do you have more solved examples with larger collections of points?