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!



Feasibility of a list of prescribed distances in R^3
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.


