# Embedding of Two Objects Into Higher Dimensions With Their Sum

Given two vector sets, $\vec x_i$ and $\vec y_i$ (for $i$=1,2,...N, but the dimensionality of each vector can be more than N), let their sum set be $\vec z_i = \vec x_i + \vec y_i$. It's easy to compute the scalar inter-distances: $x_{ij} = \Vert{\vec x_i-\vec x_j}\Vert$, $y_{ij} = \Vert{\vec y_i-\vec y_j}\Vert$, $z_{ij} = \Vert{\vec z_i-\vec z_j}\Vert$.

But, what's the quickest computation method to go backwards (i.e., from all of the inter-distances to any "high-dimensional embedding")? It seems I'm forced into ugly numerical "trial and error" methods even for small N=4 though there are easy analytical methods (for any N) if I didn't need to match the sum's inter-distances.

-
For a specific example, suppose there are 4 vectors in each set, so all 3 sets could be embedded individually as pyramids in our 3-D space. But, if those 4 vectors each actually consist of 5 numbers, we probably need 4-D to simultaneously embed all 3 objects as a sum. –  bobuhito Aug 18 '13 at 3:27
Presumably you meant: $y_{ij} = \Vert{\vec y_i-\vec y_j}\Vert$. –  Joseph O'Rourke Aug 18 '13 at 15:16
Yes, thanks, I corrected it. –  bobuhito Aug 18 '13 at 16:26

Suppose $y_i=0$ for all $i$. Then $z_i = x_i$, $y_{ij}=0$, $z_{ij}=x_{ij}$, and in this special case, your problem reduces to reconstructing $x_i$ from the interpoint distances $x_{ij} = \Vert{\vec x_i-\vec x_j}\Vert$. This is a known NP-hard problem, as discussed in earlier MO questions ("Difference Sets" and "Feasibility of a list of prescribed distances in R^3"). So I think your problem cannot be easier than this intractible special case.