The chords' problem

The chords' problem is a variant of an old problem of computational geometry: given a set of points of R-n, one can easily build the multiset of the distances between the points of the set but the converse construction is known, for a longtime, as to be difficult. The problem that we are going to investigate is also a converse construction with the difference that it is not one of the distances' multisets but one of the chords' multisets. In dimension 1, the old distances' problem and the chords' problem coincide with each other whereas in other dimensions, the chords' multisets contain more information on the sets than their distances' multisets. This paper provides, in dimension 1, two different algorithms to reconstruct the set of points according to their chords' multiset. The first one is given for its effectiveness in spite of an uncertain complexity whereas the second one is the first polynomial algorithm solving the chords' problem. At least, we will explain how to transform a chords' problem in dimension n into an equivalent chords' problem in dimension 1. (C) 2002 Elsevier Science B.V. All rights reserved.