## Reconstructing an Euclidean point cloud from their pairwise distances

I have a collection of points $P_1, ..., P_N$ in some Euclidean space $\mathbb R^m$ and the coordinates $x_1, x_2, ..., x_N$ respectively associated with them, where $x_i$ is the usual Cartesian tuple $x_i = (x_{i1}, x_{i2}, ..., x_{im})$. I can immediately calculate the pairwise distances between these points $r_{12}, r_{13}, ..., r_{N-1,N}$ under the usual Euclidean norm using Pythagoras' theorem (in $m$ dimensions), i.e. $r_{ij} = \left\Vert x_i - x_j \right\Vert$.

Suppose now I have the converse situation where I have the points $P_1, ..., P_N$ and all their associated pairwise distances $\{r_{ij}\}$, and I don't know their coordinates. What is known about the embeddability of these points in an Euclidean space, and is it possible to reconstruct the Cartesian coordinates for them? In other words, given an arbitrary collection of nonnegative numbers $\{r_{ij}\}$, how do I find all positive integers $m$ and enumerate all the possible sets of $N$ coordinates $x_1, x_2, ..., x_N \in \mathbb R^m$ that are consistent with the interpretation $r_{ij} = \left\Vert x_i - x_j \right\Vert$?

-
I think it's at least the fourth time this question has been asked here. – Gjergji Zaimi May 21 2012 at 23:54
If I may point to my answer to one of these previous questions: mathoverflow.net/questions/7794/76487#76487 . Short version: The problem is NP-hard; search under the phrase "distance geometry." – Joseph O'Rourke May 22 2012 at 0:03
@Joseph - thank you, I had the feeling that I was missing some magic incantation to find the relevant literature. – Jiahao Chen May 22 2012 at 6:05
@Gjergji my apologies for the duplication. FWIW I did try to search for this question but I didn't quite turn up anything on my own. – Jiahao Chen May 22 2012 at 6:11

If your distances are known exactly, the feasibility follows from the positive (semi) definiteness of the associated gram matrix (put one of the points, call it $p_0$ at the origin, then the $ij$-th entry equals $2 = d(P_i, P_0)^2 + d(P_j, P_0)^2 - d(P_i, P_j)^2).$ The reconstruction problem is a little tricky, and usually in practical applications, you either don't know all distances, all don't know them exactly. See this paper for a nice survey. (DISTANCE MATRIX RECONSTRUCTION FROM INCOMPLETE DISTANCE INFORMATION FOR SENSOR NETWORK LOCALIZATION), but be warned that this is a huge field, as "distance matrix reconstruction" or "multi-dimensional scaling" google searches will show.

-

It is worth mentioning the following basic material.

Definition (Euclidean Distance Matrix or EDM). A real, symmetric, $n\times n$ matrix with elements $-\tfrac{1}{2}d_{ij}^2$ and a zero diagonal is called an EDM, if there exist $n$ points in some Euclidean space whose interpoint distances are $d_{ij}$.

Theorem (Schoenberg, 1935). A real, symmetric, $n\times n$ matrix with a zero diagonal is an EDM, if and only if the matrix $$M := (I-\tfrac{1}{n}ee^T)D(I-\tfrac{1}{n}ee^T),$$ is positive semidefinite (here $e$ denotes the vector of all ones).

Note 1: The above result opens paths into the study of radial positive definite functions.

Note 2: Igor mentioned the actual interesting problems related to EDMS are more along the lines of EDM Completion Problems (EDMCP), or multidimensional scaling (obtaining an embedding into Euclidean space with some error, in case an exact embedding does not exist, and so on).

-

.... R cmdscale

-
 "Impenetrability!", as Humpty Dumpty said. – Gerald Edgar May 22 2012 at 0:05 I believe that the poster means that the OP should use the cmdscale command in the R system for statistical computing. – Igor Rivin May 22 2012 at 0:30 I beleive that if that's what the poster means, then that's what the poster should say. – Gerry Myerson May 22 2012 at 6:13 @Gerry: no argument there – Igor Rivin May 22 2012 at 12:19