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

I am puzzled with the following problem:

Given $n$ real numbers it is to obtain a Yes/No answer to: "whether it is possible to arrange different points in the Euclidean $\mathbb{R}^3$ so that every of the given numbers represents a shortest distance which belongs to a distinct pair of points?"

What is an efficient algorithm to solve such problem? If I understand properly, first I have to find $m$ from $n=\frac{m(m+1)}{2}$ which is the number of such points. But what is the next step? Should I deal with checking the triangle inequality (which seems to be very inefficient) or what?

Thank you in advance!

share|improve this question
3  
You really need to use better titles. The one you have right now is completely useless. I recommend having a title in the form a question (of course, sometimes that doesn't make sense, but I think it shouldn't be so hard for this one). –  Ben Webster Dec 4 '09 at 18:46
1  
I did something about that. –  Greg Kuperberg Dec 4 '09 at 20:06
add comment

5 Answers 5

up vote 13 down vote accepted

Let us label the points $x_0,x_1,\dots,x_m$. For each pair $(x_i,x_j)$ prescribe the a value from your list; denote it by say $d(x_i,x_j)$. If there are no repititions then all together you have $N=[m{\cdot}(m+1)]!$ ways to do this.

Note that $d(x_i,x_j)$ completely determine "$m\times m$-matrix of scalar products" $$a_{ij}=\tfrac12\cdot[d^2(x_0,x_i)+d^2(x_0,x_j)-d^2(x_i,x_j)].$$

You need to answer two questions for each of obtained $N$ matrices:

  • $(a_{ij})$ defines a non-negative quadratic form

  • $\mathop{\rm rank}(a_{ij})\leqslant 3$.

If for one matrix the answers are YES to both then the answer to your question is also YES (and vise versa).

share|improve this answer
1  
My answer below is basically equivalent to this. –  Darsh Ranjan Dec 4 '09 at 22:08
    
Thank you. However it is not efficient solution, I suppose it should exist another computationally effective solution. –  psihodelia Dec 5 '09 at 22:55
    
Well checking particular matrix is computationally easy, the only problem is that one has to check all possible finite metric spaces with given distances. –  Anton Petrunin Dec 6 '09 at 21:01
add comment

What did not seem to be mentioned in this old thread is that this is a well-studied problem that goes under the name distance geometry, which Wikipedia defines as "the characterization and study of sets of points based only on given values of the distances between member pairs." The problem has applications especially to molecular structure. Crippen and Havel published a book on this in 1988: Distance geometry and molecular conformation (Research Studies Press, Taunton, Somerset, England), with an update by Crippen later ("Chemical distance geometry: Current realization and future projection"). There are many papers on the topic, published in venues like the Journal of Computational Chemistry, e.g., "Molecular conformations from distance matrices" (Volume 14, Issue 1, pages 114–120, January 1993). Because of the many applications, there are software packages developed to solve the problem; the Wikipedia article has a list. The problem is computationally intractable; the proof that one version is NP-hard goes back to a 1979 paper by Saxe, "Embeddability of weighted graphs in $k$-space is strongly NP-hard."

share|improve this answer
    
Thank you! Your info is very helpful! –  psihodelia Nov 27 '11 at 17:54
add comment

Embedded in Anton's answer are the following two aspects of the problem:

  • You first need to decide (or be given) the combinatorial structure of the graph you want to embed, i.e., assign the n distances to the n pairs of points in some way. There will be some symmetries, but not enough to avoid this step; even when m = 4, n = 6, you need to decide which pairs of edges of the tetrahedron will be opposite.

  • Once you have done that, checking the triangle inequality for all triples of points is not sufficient. For example, consider 5 points in R4 which do not lie in a hyperplane. The 10-tuple of distances between these points determines the set of 5 points up to a rigid motion (or reflection) of R4. In particular, we cannot find 5 points in R3 with the prescribed distances between pairs. Yet obviously all the triangle inequalities are satisfied.

share|improve this answer
    
To expand on Reid's second bullet point, although the triangle inequality is not enough, there is something similar which is: checking that the matrix in Anton's answer is positive definite of rank 3. The triangle inequality can be understood as checking that every principal 3x3 minor is positive definite, a related but clearly weaker condition. –  David Speyer Dec 9 '09 at 12:00
add comment

This isn't a complete answer, but it might shed some light on what is involved.

Let $n=m(m-1)/2$, and let's say you've decided which pairs of the $m$ points should get which of the $n$ distances. You should form the $m\times m$ matrix $M$ whose entries are the squared distances, i. e., $M\_{ij}=||x\_i-x\_j||^2$, where the $m$ (unknown) points are $x\_1,\ldots,x\_m$. Suppose the $m$ points all belong to $\mathbb{R}^k$. Let $X$ be the $k\times m$ matrix whose $j$-th column is $x\_j$. Without loss of generality, the points have mean zero, so $x\_1 + \ldots + x\_m = X\alpha^T = 0$, where $\alpha=(1,\ldots,1)$. It's easy to show that if $P=I-\frac1m\alpha \alpha^T$ is the orthogonal projection onto the orthogonal complement of $\alpha$, then $PMP = -2X^TX$. Thus, once you know $M$, you can attempt to find $X$ by a modification of Cholesky decomposition applied to $-\frac12PMP$. You need to modify the procedure to make it return a $k\times m$ matrix, not an $m\times m$ matrix. (Since you want $\mathbb{R}^3$, you should take $k=3$.) If it succeeds, then you have a solution; otherwise, no solution exists.

Unfortunately, that assumes that you've assigned the $n$ distances to pairs of points already. If the above procedure fails, then it's still completely possible that some other assignment of distances to pairs will yield a solution. I'm not seeing any easy way to solve this; checking all possible assignments is out of the question even for pretty modest values of $m$ even if you can break all the symmetries, since I think you would need to check $(m(m-1)/2)!/m!$ assignments in the worst case. Maybe there's a way to reduce the number of permutations you need to check, but I'm not seeing it.

share|improve this answer
    
Thank you. I suppose however that there must be a more simple and computationally effective method. –  psihodelia Dec 5 '09 at 23:05
add comment

I think the following paper deals with this question:

Metric Spaces and Positive Definite Functions by: I. J. Schoenberg Transactions of the American Mathematical Society, Vol. 44, No. 3. (nov 1938), pp. 522-536.

There is a book of Schoenberg's papers on google books and if you search on the title you ought to be able to read this paper.

share|improve this answer
1  
I read this paper recently and unless I missed something, I don't think it answers this question. What it does answer is a related question: which square matrices are the distance-matrices of some finite subset of R^n? Maybe one could use that to help answer psihodelia's question. –  Tom Leinster Dec 6 '09 at 18:24
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.