Best way to determine the minimum dimension of a structure given only distances between points 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.
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&gt;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