2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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)$ ? $\endgroup$ – Paul Jul 5 '12 at 20:27
  • $\begingroup$ 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. $\endgroup$ – usero Jul 5 '12 at 21:32
  • $\begingroup$ Could you provide a link to the other paper? $\endgroup$ – Paul Jul 6 '12 at 0:04
  • $\begingroup$ @Paul Link: springerlink.com/content/0725vul28l764048 $\endgroup$ – usero Jul 6 '12 at 8:11
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks. You'd be surprised on how many places I've found the incorrect statement from the first reference cited in my question. $\endgroup$ – usero Jul 6 '12 at 13:55
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ So, the second formula is the correct one? Any reference? Note that this author has mis-typed it once more: jstor.org/discover/10.2307/… (p4, left column) $\endgroup$ – usero Jul 6 '12 at 8:32
  • $\begingroup$ I see that you already got an answer so I don't know how helpful this comment will be. I was simply making an argument based on the fact that they were different, so only one could be correct. I was choosing the first equation based on the fact that it gave fractional answers to a problem in which only integer values made any sense at all. I didn't have any reference for supporting the other equation as correct. $\endgroup$ – Godric Seer Jul 6 '12 at 16:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.