15
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ I assume you want an embedding into $\ell_2$ ? $\endgroup$
    – Suresh Venkat
    Commented Nov 25, 2011 at 8:31
  • $\begingroup$ @Suresh: Yes, sorry, I meant to add that. $\endgroup$
    – Joe Fitzsimons
    Commented Nov 25, 2011 at 8:33
  • 1
    $\begingroup$ What's the area of physics where this comes from, btw? $\endgroup$
    – Vinayak Pathak
    Commented Nov 25, 2011 at 14:12
  • $\begingroup$ @Vinayak: I just came across it when trying to calculate something in quantum mechanics. $\endgroup$
    – Joe Fitzsimons
    Commented Nov 25, 2011 at 17:25
  • 1
    $\begingroup$ math.stackexchange.com/q/4533475/14578 $\endgroup$
    – D.W.
    Commented Oct 28, 2023 at 4:58

2 Answers 2

Reset to default
16
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – Joe Fitzsimons
    Commented Nov 25, 2011 at 17:11
12
$\begingroup$

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. 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.

Improve this answer
$\endgroup$
6
  • 1
    $\begingroup$ Great, this might be just the pointer I needed. Sorry to waste your time if this is a somewhat trivial question. $\endgroup$
    – Joe Fitzsimons
    Commented Nov 25, 2011 at 9:03
  • 1
    $\begingroup$ It's not trivial if you don't muck around in distance geometry :) $\endgroup$
    – Suresh Venkat
    Commented Nov 25, 2011 at 9:09
  • $\begingroup$ 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? $\endgroup$
    – Joe Fitzsimons
    Commented Nov 25, 2011 at 9:25
  • 1
    $\begingroup$ Ah the problem I realize is that it doesn't handle the partial case. :( $\endgroup$
    – Suresh Venkat
    Commented Nov 25, 2011 at 17:57
  • 1
    $\begingroup$ @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. $\endgroup$
    – Tsuyoshi Ito
    Commented Nov 26, 2011 at 1:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.