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

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.

Answer 2

not sure it has a name; more formally stated, it would be:

|a-b| = 100
|c-b| = 20
|c-d| = 90
|a-d| = 170

where |x| stands for the absolute value of x

As far as the generalized system goes, if you have N equations of this type with k unknowns, you have N choices of sign. Without loss of generality (because any solution yields a second solution with reversed ordering) you can choose a sign for the first equation, and a particular value for one of the unknowns (since the whole thing can slide left and right in position). Then you have 2^N-1 possibilities for the remaining equations, and all you have to do is go through them to see which ones, if any, have solutions. Because the coefficients are all +/- 1 and each equation has 2 unknowns, you just go through them one by one:

Step 1: Without loss of generality, 
  choose a sign for one equation
  and pick a value for one unknown:
a-b = 100, a = 0

Step 2: Choose signs for the remaining absolute values.
a = 0
a-b = 100
c-b = 20
c-d = 90
a-d = 170

Step 3: go through them one by one to solve / verify there aren't conflicts 
(time = N steps).
0-b = 100  =>  b = -100
c-b = 20   =>  c = -80
c-d = 90   =>  d = -170
a-d = 170  =>  OK        => (0,-100,-80,-170) is a solution

Step 4: if this doesn't work, go back through the possible choices of sign 
and try again, starting at step 2.

Full set of solutions is (0,-100,-80,-170) 
and its negation (0,100,80,170) and any number x<sub>0</sub> added to all terms.

So an upper bound for the runtime is O(N * 2^N-1) ≡ O(N * 2^N).

I suppose there could be a shortcut but no obvious one comes to mind.

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

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 5

algebra...

or it may be a simplification of the traveling salesman problem