DIMACS TR: 2002-37
Reconstructing Sets From Interpoint Distances
Authors: Paul Lemke, Steven S. Skiena and Warren D. Smith
Which point sets realize
a given distance multiset?
Interesting cases include the ``turnpike problem'' where the
points lie on a line, the ``beltway problem'' where the points
lie on a loop, and multidimensional versions.
We are interested both in the algorithmic problem of determining such
for a given collection of distances and the combinatorial problem of
finding bounds on the maximum number of different solutions.
These problems have applications in genetics and
We give an extensive survey and bibliography in an effort to connect
the independent efforts of previous researchers, and
present many new results.
In particular, we give improved combinatorial bounds for the turnpike and
We present a pseudo-polynomial time algorithm as well as a practical
$\bigo ( 2^n n \log n )$-time algorithm that find all solutions to the
turnpike problem, and show that certain other variants of the
problem are NP-hard.
We conclude with a list of open problems.
Paper Available at:
DIMACS Home Page