# 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
– usero Jul 6 '12 at 8:11

## 2 Answers

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.

-

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

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.

-

– usero Jul 6 '12 at 8:32
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. – Godric Seer Jul 6 '12 at 16:03
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 15, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9469262957572937, "perplexity_flag": "head"}