Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

There is N points on a plane. Is is feasible to reproduce there relative location having only 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 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).

share|improve this question
2  
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." –  Joseph O'Rourke Jul 14 '12 at 12:10
1  
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? –  janst Jul 14 '12 at 13:08
add comment

1 Answer

up vote 12 down vote accepted

There exists examples of different point configurations in $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 you question, but actually it would be natural if in your question you also require that the distances come with their multiplicities.

share|improve this answer
    
Thank you, Joseph, for adding the picture –  Vladimir S Matveev Jul 14 '12 at 18:38
    
My pleasure! :-) –  Joseph O'Rourke Jul 14 '12 at 19:45
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.