Dimensionality of space given N points and distances between them [duplicate]

A dilettante question here.

Let's say we have N points and distances between them. All distances are non-zero and are defined for all pairs.

What should be the dimensionality of space where all points can be properly placed, given the distances between them?

I think there are two subquestions here: (1) what should be the dimensionality in a general case, i.e. given arbitrary distances? and (2) how can dimensionality be reduced in specific cases, i.e. with specific constant distances? I'm more interested in (1). So:

For 2 points the 1-dimensional space is sufficient.

For 3 points it would be a triangle in the 2-dimensional space.

However the 4-point case already seems complicated to me, since (intuitively) the 3-dimensional space is not sufficient for placing 4 points. We can form 2 triangles with a shared side, meaning that the distance between the two "free-hanging" vertices can not have an arbitrary distance between them. If this is correct, does it mean the 4-dimensional space would be sufficient?

And finally, what about N number of points with arbitrary distances between them?

• Euclidean distance? – mvw Aug 5 '18 at 8:27
• @mvw I don't know of any others :) – mojuba Aug 5 '18 at 8:30
• This problem seems to be: Given all $\DeclareMathOperator{dist}{dist}\dist(P_i, P_j)>0$ for $N$ points $P_i$, decide if it is possible to assign $n$ dimensional coordinates to each point, such that the given distances result. – mvw Aug 5 '18 at 8:34
• @mvw I think my question is slightly different: what is the smallest dimensionality where coordinates can be assigned to all points given arbitrary distances? I.e. the general case. – mojuba Aug 5 '18 at 8:40
• Does this answer your question? Minimum dimension to hold $N$ points with given distances? – Rosie F Feb 9 at 20:57

1 Answer

We assume that we are using Euclidean spaces. The problem with "given arbitrary distances" becomes apparent with 3 points. The three distances must satisfy the triangle inequality, thus the distances can not be completely arbitary. This requirement does not depend on the dimension of the Euclidean space. That is, if the triangle inequality is not satisfied, there is no way to embed the 3 points in any Euclidean space. Read the Wikipedia article Inner product space.

A similar situation arises for 4 points which you mentioned. The distance between the two "free-hanging" vertices can not have an arbitrary distance. It has to satisfy an inequality also. Similarly, if that inequality is not satisfied, there is no way to embed the 4 points in any Euclidean space. Read the Wikipedia article Ptolemy's theorem for details about Ptolemy's inequality.

• OK, but is there a proof that no such Euclidean space exists for arbitrary distances between, say, only 3 points? N points? – mojuba Aug 5 '18 at 15:57