Reconstructing sets from interpoint distances (extended abstract)

We consider the problem of determining which point sets in some given space realise a given distance multiset. Special cases include the “turnpike problem” where the points lie on a line, and the “beltway problem” where the points lie on a loop. Of interest is 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 find applications in many fields, including genetics and crystallography.