7
$\begingroup$

There are N points on a plane. Is it feasible to reproduce their relative location having only the list of distances. Assuming that translation, rotation and mirror are allowed in the result. The list contains only distances between every pair of points, but not which points these are.

For a simple triangle like A=(0,0) B=(1,0) C=(1,1) the distance are:
|AB| = 1
|AC| = sqrt(2)
|BC| = 1

The list would be: 1, 1, sqrt(2).

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ See the earlier MO question, "Reconstructing an Euclidean point cloud from their pairwise distances" mathoverflow.net/questions/97611 , which refers to even earlier MO questions. As I said there: Short version: The problem is NP-hard; search under the phrase "distance geometry." $\endgroup$
    – Joseph O'Rourke
    Commented Jul 14, 2012 at 12:10
  • 1
    $\begingroup$ Yes, I have seen that question. This version of the problem lacks the information about point for which distance is given. Isn't that a problem? $\endgroup$
    – janst
    Commented Jul 14, 2012 at 13:08

2 Answers 2

Reset to default
21
$\begingroup$

There exists examples of different point configurations in $\mathbb{R}^2$ having the same the set (but different matrices of!) distances. The simplest example contains 4 points and could be found in the paper of Boutin and Kemper, see http://arxiv.org/pdf/math/0304192v1.pdf -- scroll to page 5 to see the picture [Added by J.O'Rourke]:
     Fig4

It is shown though (also Kemper, I believe) that for most configurations the set of distances determine the configuration (which is probably intuitively expected).

The example I have mentioned answers your question, but actually it would be natural if in your question you also require that the distances come with their multiplicities.

Improve this answer
$\endgroup$
1
  • $\begingroup$ My pleasure! :-) $\endgroup$
    – Joseph O'Rourke
    Commented Jul 14, 2012 at 19:45
4
$\begingroup$

Complementing the counterexample in Vladimir S Matveev's answer, the recent preprint Determining Generic Point Configurations From Unlabeled Path or Loop Lengths by Gkioulekas, Gortler, Theran, and Zickler, finds a positive answer under certain circumstances to a generalized question.

First, they treat all dimensions $d\geq2$, and second, the list of distances provided (the "measurement set") does not necessarily correspond to the distances between pairs of points, but may also be the lengths of arbitrary paths and loops on the complete graph on the point set.

The main result roughly states that provided: (1) the measurements come from a generic point set (thus ruling out examples like the one in Vladimir S Matveev's answer) and (2) the list of measurements "allows for trilateration" (meaning that there are enough measurements to inductively construct full-dimensional simplices), there is a unique point configuration (up to congruence) consistent with the measurements.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Also note the mention of this MO question mathoverflow.net/questions/259664 in section 6.3 on the linear automorphisms of the "unsquared measurement variety". $\endgroup$
    – j.c.
    Commented Sep 13, 2017 at 19:23
  • 1
    $\begingroup$ The Boutin-Kemper result shows that, under the same genericity hypothesis as the preprint you link to, the unordered set of distances from a complete graph determine the configuration. In fact, many fewer pairwise distances suffice generically, as shown in the the preprint arxiv.org/abs/1806.08688 $\endgroup$
    – Louis
    Commented Oct 21, 2018 at 2:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .