1

Problem Statement: Given the (x, y) coordinates of k points, out of all the possible ways to make k/2 pairs of distinct links between two distinct points, find the minimum possible sum of distances for the links in the graph. K is always an even positive integer.
My Approach

I've analysed that this involves generating all possible permutations of points and out of those, i'll have to select the one for which the sum of distances is the least. But this will result in an overall complexity of O(k!). The value of k can be at max 16. Hence, 16! will be a very big number.

Is there any other way to approach this problem which has a better complexity ?This is not my homework. I just want to know if any other standard algorithm exists for similar kind of problems apart from brute force.

Update: I found a very similar kind of problem here. Is this correct?

2
  • Yup, this is it.
    – cadolphs
    Sep 28, 2021 at 3:27
  • Okay. Please don't close this question for sometime. If incase i need to ask anything else, i'll post here.
    – taurus05
    Sep 28, 2021 at 3:35

1 Answer 1

0

Let's assume that initially all the points are not marked. Do the following steps until there are no unmarked points left: Find a pair of points among the not yet marked ones with the smallest distance between them in O(n^2). Mark the 2 points found and add to the answer a distance between them. Such a cycle will work n/2=O(n) times, therefore, the total complexity of the algorithm will be O(n^2*n)=O(n^3).

4
  • Finding a single pair with the smallest distance needn't take O(n^2). It's a 2D 'closest pair' problem for which a linealogarithmic solution is known. This makes a total complexity O(n^2 log n).
    – CiaPan
    Sep 28, 2021 at 11:16
  • But we can iterate over each point and iterate through the remaining ones in a nested loop. Therefore, the complexity of such a search is O(n^2)
    – pavel
    Sep 29, 2021 at 7:42
  • Yes, that's true. You can do that in even longer time, if you want.
    – CiaPan
    Sep 29, 2021 at 10:30
  • Be aware this algorithm does not guarantee to find the minimum sum, as required by the problem statement. Suppose four points on the X axis, at x equal 0, 10, 11 and 20. The closest pair is (10, 11) with the distance of 1. After you remove it, only (0, 20) remains with the distance of 20. Result: 21. But the correct answer would be 19, for (0, 10) and (11, 20).
    – CiaPan
    Sep 29, 2021 at 13:02

Your Answer

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

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