What is the name of this problem?

Question

You are given a list of distances between various points on a single line.

For example:

• 100 between a and b
• 20 between c and b
• 90 between c and d
• 170 between a and d

Return the sorted sequence of points as they appear on the line with distances between them:

For example the above input yields: a<----80-----> c <----20------> b <----70-----> d or the reverse sequence(doesn't matter)

What is this problem called? I would like to research it.

If anybody knows, also, what are some of the possible asymptotic runtimes achieved for this?

Answer 1

algebra...

or it may be a simplification of the traveling salesman problem

Answer 2

I don't have an algorithms book handy, but this sounds like a graph search problem where the paths are constrained. You could probably use Dijkstra's Algorithm or some variant of it.

Answer 3

As written, your problem is just a system of non-linear equations (expressed with absolute values or quadratic equations). However, it looks similar to the problems of finding Golomb rulers or perfect rulers.

If you consider your constraints as quadratic equations eg. (a-b)^2=100^2, then you can formulate this as a quadratic programming problem and use some of the well-studied techniques for that class of problem.

Answer 4

Considering the sign of the direction of each segment X[i] -> X[i+1] it becomes a boolean satisfiability problem. I can't see an obvious simplification. The runtime is O(2^N) - specifically 2^(N-2) tests with N values and an O(1) expression to test.

Assuming a = 0 and fixing the direction of a -> b:

a = 0
b = 100
c = b + 20 X[0] = 100 + 20 X[0]
d = c + 90 X[1] = 100 + 20 X[0] + 90 X[1]
test d == 170

where X[i] is either +1 or -1.

Although the expression for d appears to require O(N) operations ( (N-2) multiplications and (N-2) additions ), by using a Gray code or other such mechanism for changing the state of only one X at a time so the cost can be O(1) per test. ( though for N=4 it probably isn't worth it )

Simplifications may arise if you either have more constraints than points - if you were given |b-d| == 70, then you only need tests two cases rather than four - essentially b,c and d become their own fully constrained sub-problem.

Simplifications may also arise from the triangular property

| |a-b| - |b-c| | <= |a-c| <= |a-b| + |b-c| for all a, b and c.

So if you have many points, and you know the total of the distances between the points up to a certain point given the assignments made to X, and that total is further from the target value than the total of the distances between the remaining points, you can then deduce that there is no combination of assignments of the remaining points which will work.