# 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