mg.metric geometry - Feasibility of a list of prescribed distances in R^3

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 $mtimes 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 $ktimes m$ matrix whose $j$-th column is $x_j$. Without loss of generality, the points have mean zero, so $x_1 + ldots + x_m = Xalpha^T = 0$, where $alpha=(1,ldots,1)$. It's easy to show that if $P=I-frac1malpha 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 $ktimes m$ matrix, not an $mtimes 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.