DIMACS TR: 2002-37

Reconstructing Sets From Interpoint Distances



Authors: Paul Lemke, Steven S. Skiena and Warren D. Smith

ABSTRACT

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 point sets 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 crystallography.

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 beltway problems. 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: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2002/2002-37.ps.gz

DIMACS Home Page