<p>This problem is sometimes called the low-dimensional Euclidean distance matrix completion or the low-dimensional Euclidean embedding of a weighted graph.</p>

<p>Saxe [Sax79] and Yemini [Yem79] independently showed by a simple reduction from the Partition problem that this problem is NP-complete even in the case of one dimension; that is, the following problem is NP-complete for <i>k</i>=1:</p>

<p><strong><i>k</i>-dimensional Euclidean distance matrix completion / <i>k</i>-dimentional Euclidean embedding of a weighted graph</strong><br>
<em>Instance</em>: A symmetric matrix <i>M</i> whose entries are either positive integers in binary or “unknown.”<br>
<em>Question</em>: Can the unknown entries in <i>M</i> be filled by real numbers so that <i>M</i> becomes a distance matrix of points in the <i>k</i>-dimensional Euclidean space ℝ<sup><i>k</i></sup>?<br>
Equivalently,<br>
<em>Instance</em>: A graph <i>G</i> where each edge has a positive integer weight written in binary.<br>
<em>Question</em>: Can the vertices of <i>G</i> placed in the <i>k</i>-dimensional Euclidean space ℝ<sup><i>k</i></sup> so that for each edge of <i>G</i>, the distance between the two endpoints equals to the weight of the edge?</p>

<p>Moreover, Saxe [Sax79] showed (by a more involved reduction from 3SAT) that the <i>k</i>-dimensional Euclidean distance matrix completion remains NP-hard even under the restriction that all known entries in <i>M</i> are either 1 or 2, for every positive integer constant <i>k</i>.  In particular, the problem is NP-complete even when the known entries in <i>M</i> are given in unary.  [Sax79] also contains some hardness results about approximate embedding.</p>

<p>By the way, I do not think that it is trivial that the problem is in NP; note that you need irrational coordinates in some cases when <i>k</i>&gt;1.  I do not know if it is known to be in NP.</p>

<h3>References</h3>

<p>[Sax79] James B. Saxe.  Embeddability of weighted graphs in <i>k</i>-space is strongly NP-hard.  In <em>Proceedings of the 17th Allerton Conference on Communications, Control, and Computing</em>, pp. 480–489, 1979.  Also in James B. Saxe: <em>Two Papers on Graph Embedding Problems</em>, Department of Computer Science, Carnegie-Mellon University, 1980.</p>

<p>[Yem79] Yechiam Yemini.  Some theoretical aspects of position-location problems. In <em>20th Annual Symposium on Foundations of Computer Science (FOCS)</em>, pp. 1–8, Oct. 1979.  DOI: <a href="http://dx.doi.org/10.1109/SFCS.1979.39" rel="noreferrer">10.1109/SFCS.1979.39</a></p>

CC BY-SA 3.0
2011-11-25T17:11:10.627Z
Thanks. Certainly in the general case it is not obviously in NP, but if you turn it into a promise problem by restrict points to lying on a lattice, and instead are given the square of the distances, rather than the distances themselves, then all square distances are integers, and so a solution can be checked exactly in polynomial time.
Joe Fitzsimons
CC BY-SA 3.0
2011-11-25T15:15:26.707Z
2011-11-27T15:33:45.370Z
2011-11-27T15:33:45.370Z
Tsuyoshi Ito
<p>Given a fixed $d$, there is a precise characterization of distance matrices that represent distances between $n$ points in $d$ dimensions. This comes from a theorem of Schoenberg and relates <a href="http://geomblog.blogspot.com/2009/08/negative-type-distances-and-kernels.html">kernels in ML and negative-type distances</a>.  This characterization can be tested in polynomial time (it involves computing rank and testing for negative definiteness). I believe it also follows from this that if there exists an embedding into Euclidean space, this embedding will be in no more than $n$ dimensions.</p>

CC BY-SA 3.0
2011-11-25T09:03:51.713Z
Great, this might be just the pointer I needed. Sorry to waste your time if this is a somewhat trivial question.
Joe Fitzsimons
CC BY-SA 3.0
2011-11-25T09:09:15.447Z
It's not trivial if you don't muck around in distance geometry :)
Suresh Venkat
CC BY-SA 3.0
2011-11-25T09:25:22.450Z
I've read your post, and it certainly seems to point me in the right direction. However, I'm not entirely clear how this would apply with only a partial set of distances. Could you enlighten me?
Joe Fitzsimons
CC BY-SA 3.0
2011-11-25T17:57:15.620Z
Ah the problem I realize is that it doesn't handle the partial case. :(
Suresh Venkat
CC BY-SA 3.0
2011-11-25T18:05:14.993Z
No problem. This was still an interesting read. Do you by any chance have a reference (or more detailed explanation) for how to check the negative type inequality holds?
Joe Fitzsimons
CC BY-SA 3.0
2011-11-26T01:24:51.863Z
@Joe: A distance matrix satisfies all the negative-type inequalities if and only if the corresponding “Gram matrix” is positive semidefinite.  (I put “Gram matrix” in scare quotes because it is not really a Gram matrix unless the distance is realizable in a Euclidean space.)  However, I do not know how to handle the restriction on dimension using this approach.
Tsuyoshi Ito
CC BY-SA 3.0
2011-11-25T08:58:47.200Z
2011-11-25T08:58:47.200Z
Suresh Venkat
<p>I came across this problem in an area of physics quite far removed from computer science, but it seems like the type of question that has been studied in CS, so I thought I'd try my luck asking it here.</p>

<p>Imagine you are given a set of points $\{v_i\}_{i=1}^n$ and list of some of the distances between points $d_{ij}$. What is the most efficient way to determine the minimum dimensionality of the space in which you need to embed these points? In other words, what is the smallest $k$ such that there exist a set of points in $\mathbb{R}^k$ satisfying the distances constraints $d_{ij}$. I would be equally happy with an answer for $\mathbb{C}^k$, but this seems harder. </p>

<p>I am happy to say that the distances need to match $d_{ij}$ only to within some constant accuracy $\epsilon$ and to have the points restricted to points on some lattice of constant spacing, in order to avoid issues of computing with reals.</p>

<p>Indeed, I would be quite happy with a solution for the decision version of this problem, where given $d_{ij}$ and $k$ you are asked whether or not such a set of vertices $\{v_i\}$ exist. Trivially the problem is in NP, since given a set of points in $\mathbb{R}^k$ it is easy to check that they satisfy the distance requirements, but it feels like there should be sub-exponential time algorithms for this particular problem.</p>

<p>The most obvious approach seems to be to try to build $k$-dimensional structures iteratively, by adding additional points one at a time and determining whether or not a new spatial dimension needs to be added at each iteration. The problem with this is that it seems you can run into ambiguities where there is more than one way to add a point to the existing structure, and it is not clear which one will lead to fewer dimensions as you continue to add more points.</p>

<p>Lastly, let me say that I know that it is easy to create lists of distances which cannot be satisfied in any number of dimensions (i.e. ones which violate the triangle inequality). However, for the instances I care about there will always be some minimum finite number of dimensions in which a satisfying set of points can be found.</p>

CC BY-SA 3.0
2011-11-25T08:31:09.770Z
I assume you want an embedding into $\ell_2$ ?
Suresh Venkat
CC BY-SA 3.0
2011-11-25T08:33:27.513Z
@Suresh: Yes, sorry, I meant to add that.
Joe Fitzsimons
CC BY-SA 3.0
2011-11-25T14:12:19.567Z
What's the area of physics where this comes from, btw?
Vinayak Pathak
CC BY-SA 3.0
2011-11-25T17:25:48.273Z
@Vinayak: I just came across it when trying to calculate something in quantum mechanics.
Joe Fitzsimons
CC BY-SA 4.0
2023-10-28T04:58:04.900Z
https://math.stackexchange.com/q/4533475/14578
D.W.
<ds.algorithms><cg.comp-geom>
Best way to determine the minimum dimension of a structure given only distances between points
Joe Fitzsimons
# Best way to determine the minimum dimension of a structure given only distances between points

(Asked by: username_0 on 2011-11-25)

I came across this problem in an area of physics quite far removed from computer science, but it seems like the type of question that has been studied in CS, so I thought I'd try my luck asking it here.

Imagine you are given a set of points $\{v\_i\}\_{i=1}^n$ and list of some of the distances between points $d\_{ij}$. What is the most efficient way to determine the minimum dimensionality of the space in which you need to embed these points? In other words, what is the smallest $k$ such that there exist a set of points in $\mathbb{R}^k$ satisfying the distances constraints $d\_{ij}$. I would be equally happy with an answer for $\mathbb{C}^k$, but this seems harder.

I am happy to say that the distances need to match $d\_{ij}$ only to within some constant accuracy $\epsilon$ and to have the points restricted to points on some lattice of constant spacing, in order to avoid issues of computing with reals.

Indeed, I would be quite happy with a solution for the decision version of this problem, where given $d\_{ij}$ and $k$ you are asked whether or not such a set of vertices $\{v\_i\}$ exist. Trivially the problem is in NP, since given a set of points in $\mathbb{R}^k$ it is easy to check that they satisfy the distance requirements, but it feels like there should be sub-exponential time algorithms for this particular problem.

The most obvious approach seems to be to try to build $k$-dimensional structures iteratively, by adding additional points one at a time and determining whether or not a new spatial dimension needs to be added at each iteration. The problem with this is that it seems you can run into ambiguities where there is more than one way to add a point to the existing structure, and it is not clear which one will lead to fewer dimensions as you continue to add more points.

Lastly, let me say that I know that it is easy to create lists of distances which cannot be satisfied in any number of dimensions (i.e. ones which violate the triangle inequality). However, for the instances I care about there will always be some minimum finite number of dimensions in which a satisfying set of points can be found.

**Tags:** ds.algorithms, cg.comp-geom
> **Comments:**
> **username_1**: I assume you want an embedding into $\ell_2$ ?  
> **username_0**: @Suresh: Yes, sorry, I meant to add that.  
> **username_2**: What's the area of physics where this comes from, btw?  
> **username_0**: @Vinayak: I just came across it when trying to calculate something in quantum mechanics.  
> **username_3**: https://math.stackexchange.com/q/4533475/14578  

---

## 2 answers

### Answer by username_4 on 2011-11-25. Score: 16

This problem is sometimes called the low-dimensional Euclidean distance matrix completion or the low-dimensional Euclidean embedding of a weighted graph.

Saxe [Sax79] and Yemini [Yem79] independently showed by a simple reduction from the Partition problem that this problem is NP-complete even in the case of one dimension; that is, the following problem is NP-complete for *k*=1:

***k*-dimensional Euclidean distance matrix completion / *k*-dimentional Euclidean embedding of a weighted graph**  
*Instance*: A symmetric matrix *M* whose entries are either positive integers in binary or “unknown.”  
*Question*: Can the unknown entries in *M* be filled by real numbers so that *M* becomes a distance matrix of points in the *k*-dimensional Euclidean space ℝ*k*?  
Equivalently,  
*Instance*: A graph *G* where each edge has a positive integer weight written in binary.  
*Question*: Can the vertices of *G* placed in the *k*-dimensional Euclidean space ℝ*k* so that for each edge of *G*, the distance between the two endpoints equals to the weight of the edge?

Moreover, Saxe [Sax79] showed (by a more involved reduction from 3SAT) that the *k*-dimensional Euclidean distance matrix completion remains NP-hard even under the restriction that all known entries in *M* are either 1 or 2, for every positive integer constant *k*. In particular, the problem is NP-complete even when the known entries in *M* are given in unary. [Sax79] also contains some hardness results about approximate embedding.

By the way, I do not think that it is trivial that the problem is in NP; note that you need irrational coordinates in some cases when *k*>1. I do not know if it is known to be in NP.

### References

[Sax79] James B. Saxe. Embeddability of weighted graphs in *k*-space is strongly NP-hard. In *Proceedings of the 17th Allerton Conference on Communications, Control, and Computing*, pp. 480–489, 1979. Also in James B. Saxe: *Two Papers on Graph Embedding Problems*, Department of Computer Science, Carnegie-Mellon University, 1980.

[Yem79] Yechiam Yemini. Some theoretical aspects of position-location problems. In *20th Annual Symposium on Foundations of Computer Science (FOCS)*, pp. 1–8, Oct. 1979. DOI: [10.1109/SFCS.1979.39](http://dx.doi.org/10.1109/SFCS.1979.39)

> **Comments:**
> **username_0**: Thanks. Certainly in the general case it is not obviously in NP, but if you turn it into a promise problem by restrict points to lying on a lattice, and instead are given the square of the distances, rather than the distances themselves, then all square distances are integers, and so a solution can be checked exactly in polynomial time.  

---

### Answer by username_1 on 2011-11-25. Score: 12

Given a fixed $d$, there is a precise characterization of distance matrices that represent distances between $n$ points in $d$ dimensions. This comes from a theorem of Schoenberg and relates [kernels in ML and negative-type distances](http://geomblog.blogspot.com/2009/08/negative-type-distances-and-kernels.html). This characterization can be tested in polynomial time (it involves computing rank and testing for negative definiteness). I believe it also follows from this that if there exists an embedding into Euclidean space, this embedding will be in no more than $n$ dimensions.

> **Comments:**
> **username_0**: Great, this might be just the pointer I needed. Sorry to waste your time if this is a somewhat trivial question.  
> **username_1**: It's not trivial if you don't muck around in distance geometry :)  
> **username_0**: I've read your post, and it certainly seems to point me in the right direction. However, I'm not entirely clear how this would apply with only a partial set of distances. Could you enlighten me?  
> **username_1**: Ah the problem I realize is that it doesn't handle the partial case. :(  
> **username_0**: No problem. This was still an interesting read. Do you by any chance have a reference (or more detailed explanation) for how to check the negative type inequality holds?  
> **username_4**: @Joe: A distance matrix satisfies all the negative-type inequalities if and only if the corresponding “Gram matrix” is positive semidefinite.  (I put “Gram matrix” in scare quotes because it is not really a Gram matrix unless the distance is realizable in a Euclidean space.)  However, I do not know how to handle the restriction on dimension using this approach.  

---

