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

Question

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.

Answer 1

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.

Answer 2

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.