# A sufficient number of distances to recover relative positions of n points

On several places I found different claims on a sufficient number of distances to recover relative positions of $n$ points in $d$-dimensional space.

For instance, work from

http://www.dimitris-agrafiotis.com/Papers/jcc20078.pdf

(page 5, right column) claims that only $\left(\frac{n-d/2-1}{d+1}\right)$ distances are sufficient.

In another paper I found that $n(d+1) -(d+1)(d+2)/2$ distances are sufficient. Plugging in $n=3$ and $d=2$ yields different results (what about the result with the first paper?) What is the correct answer? A reference containing a more elaborate account would be appreciated.

• The paper you specify seems to only state the second of your two claims about the number of distances. Where did you find the first claim $\left(\frac{n-d/2-1}{d+1}\right)$ ? – Paul Jul 5 '12 at 20:27
• I guess my statement was ambiguous. Another paper makes the different claim. Note that the first claim from your comment is in the paper, at p.5, right column. – usero Jul 5 '12 at 21:32
• Could you provide a link to the other paper? – Paul Jul 6 '12 at 0:04
For $d>1$, you need to determine all distances of a simplex consisting of $d+1$ points, and then the distances from each other point to these points. ($d$ points and distances already reduce the possibilities to a finite number, but then one needs additional disambiguation information).
This makes a total of $d(d+1)/2+(n-d-1)(d+1) = n(d+1)-(d+2)(d+1)/2$ distances.
The formula from the paper is a factor of $(d+1)^2$ times smaller than the second formula you mention. Since the paper is only citing the equation as a well known fact I am going to have to argue that he simply mis-typed it, replacing the multiplication by $d+1$ with a division by $d+1$. Also, the fact that it says $1/3$ of a distance is required for the 3 point, 2-D case doesn't make any sense at all.