6
$\begingroup$

Let $P$ be a set of $n$ points. Assuming I know the pairwise distances for each pair of points. What would be the minimum dimension of the space in which I could place those $n$ points with respect to the different pairwise distances.

The idea would be to set a first point at random coordinates in a multi-dimensional space. Then, add the other $n-1$ points so that the pairwise distances are respected.

Sorry, it's maybe a trivial question for mathematicians but I'm still wondering if the relation: "number of points $\to$ minimum dimension of space" does exist.

$\endgroup$
1

3 Answers 3

13
$\begingroup$

For the basic result, start with

Wikipedia

or Google "Johnson-Lindenstrauss Lemma".

$\endgroup$
1
  • $\begingroup$ Hi, thank you for the lead. It seems to quite fit what I had in Mind. $\endgroup$
    – Castim
    Oct 29, 2011 at 18:59
9
$\begingroup$

Suppose your $\binom{n}{2}$ distances are all exactly 1. Then they determine an $(n{-}1)$-simplex in $\mathbb{R}^{n-1}$, and those distances cannot be realized in a lower dimension. For example, three points at unit distance determine an equilateral triangle in $\mathbb{R}^{2}$; four points at unit distance determine a regular tetrahedron in $\mathbb{R}^{3}$, whose six edge lengths are each 1.
            tetrahedron
Generally, the more interesting question is how to embed the distances in a space of modest dimension without significant distortion. See, e.g., the chapter by Indyk and Matoušek, "Low-distortion embeddings of finite metric spaces," Handbook of Discrete and Computational Geometry, 2018, or the 2006 paper by Bartal, "Embedding finite metric spaces in low dimension."

$\endgroup$
0
6
$\begingroup$

Obviously, for some special distances, you can embed the points in a fewer-dimensional space. If this is important, one way to count the correct dimension would be the rank of a certain matrix.

$(b-a,c-a)=(d(a,b)^2+d(a,c)^2-d(b,c)^2)/2$

If you fix a point $a$ and place the other values of this dot product into an $n-1$ by $n-1$ symmetric matrix, the rank of that matrix will be the dimension of the space you can embed the points in.

$\endgroup$

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.