@inproceedings{c20a0fb452ab422b99ba4e8d1d5c9644,
title = "Reconstructing sets from interpoint distances (extended abstract)",
abstract = "We consider the problem of determining which point sets in some given space realize 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. In this paper, we give improved combinatorial bounds for the turnpike and beltway problems in both one and higher dimensions. We present a practical algorithm which, on n points drawn at random from a real interval, finds all solutions in O (n2log n) time with probability 1. We also prove that some variants of the problem are No-complete.",
author = "Skiena, \{Steven S.\} and Smith, \{Warren D.\} and Paul Lemke",
year = "1990",
doi = "10.1145/98524.98598",
language = "English",
isbn = "0897913620",
series = "Proc Sixth Annu Symp Comput Geom",
publisher = "Publ by ACM",
pages = "332--339",
booktitle = "Proc Sixth Annu Symp Comput Geom",
note = "Proceedings of the Sixth Annual Symposium on Computational Geometry ; Conference date: 06-06-1990 Through 08-06-1990",
}