Finding positions of milestones given their pairwise distances

Question

There is a straight road with 'n' number of milestones. You are given an array with the distance between all the pairs of milestones in some random order. Find the position of milestones.

Example:

Consider a road with 4 milestones (a,b,c,d) :

a ---3Km--- b ---5Km--- c ---2Km--- d

Distance between a and b is 3

Distance between a and c is 8

Distance between a and d is 10

Distance between b and c is 5

Distance between b and d is 7

Distance between c and d is 2

All the above values are given in a random order say 7, 10, 5, 2, 8, 3.

The output must be 3, 5, 2 or 2, 5, 3.

Assuming the length of the give array is n. My idea is:

1. Calculate the number of milestones by solving a quadratic equation, saying it's x.
2. There are P(n, x-1) possibilities.
3. Validate every possible permutation.

Is there any better solution for this problem?

Answer 1

I can't find an algorithm for this that has good worst-case behaviour. However, the following heuristic may be useful for practical solution:

• Say the first landmark is at position zero. You can find the last landmark. Then all other landmark positions need to appear in the input array. Their distances to the last landmark must also appear.
• Let's build a graph on these possible landmark positions.
• If a and b are two possible landmark positions, then either |a-b| appears in the input array or at least one of a and b isn't a landmark position. Draw an edge between a and b if |a-b| appears in the input array.
• Iteratively filter out landmark positions whose degree is too small.

You wind up with something that's almost a clique-finding problem. Find an appropriately large clique; it corresponds to a positioning of the landmarks. Check that this positioning actually gives rise to the right distances.

At worst here, you've narrowed down the possible landmark positions to a more manageable set.