9
$\begingroup$

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!

$\endgroup$
3
  • 3
    $\begingroup$ 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). $\endgroup$
    – Ben Webster
    Dec 4, 2009 at 18:46
  • 2
    $\begingroup$ I did something about that. $\endgroup$ Dec 4, 2009 at 20:06
  • $\begingroup$ This is related to what is called multidimensional scaling in statistics $\endgroup$ Apr 19, 2018 at 7:43

5 Answers 5

18
$\begingroup$

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).

P.S. Apparently the statement I used is called Schoenberg criterion; thanks to Piotr Hajlasz for pointing this out.

$\endgroup$
10
  • 1
    $\begingroup$ My answer below is basically equivalent to this. $\endgroup$ Dec 4, 2009 at 22:08
  • $\begingroup$ Thank you. However it is not efficient solution, I suppose it should exist another computationally effective solution. $\endgroup$
    – psihodelia
    Dec 5, 2009 at 22:55
  • $\begingroup$ Well checking particular matrix is computationally easy, the only problem is that one has to check all possible finite metric spaces with given distances. $\endgroup$ Dec 6, 2009 at 21:01
  • $\begingroup$ @AntonPetrunin This is related to a result of Schoenberg, isn't it? You should give appropriate references as otherwise your answer is of limited use. $\endgroup$ Apr 17, 2018 at 17:14
  • $\begingroup$ @PiotrHajlasz I am not aware of this --- feel free to modify my answer $\endgroup$ Apr 17, 2018 at 23:05
12
$\begingroup$

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."

$\endgroup$
0
5
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Dec 9, 2009 at 12:00
5
$\begingroup$

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.

$\endgroup$
0
3
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$ Dec 6, 2009 at 18:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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