8
$\begingroup$

Erdos in his Distinct distance Problem in a plane conjectured that the minimal number of distinct distance determined by $n$ points in a plane be $g(n)$,

$$g(n) \sim \frac{cn}{\sqrt{\log n}}$$

But for the special case which asks the minimum number of distinct distances that must be determined by $n$ points in a plane such that no $3$ are collinear be $g_{\textrm{no}3}(n)$, it is known that,

$$g_{\textrm{no}3}(n) \ge \left\lceil \frac{n-1}{3} \right\rceil$$

and $\displaystyle g_{\textrm{gen}}(n) \ge \left\lceil \frac{n-1}{3} \right\rceil$, where, $g_{\textrm{gen}}(n)$ asks the same question but for points in general position in a plane (i.e., no $3$ collinear and no $4$ conclyclic.)

Has there been any improvements on these particular casees of Erdos's Distance Problem?

$\endgroup$

2 Answers 2

8
$\begingroup$

Here is a survey only four weeks old:

Sheffer, Adam. "Distinct distances: open problems and current bounds." arXiv:1406.1949 (2014). (arXiv abstract).

It is not known whether $D_{gen}(n)=\Theta(n)$ ($\Omega(n)$ is trivial), and the current best upper bound is $n 2^{O( \sqrt{\log n} )}$.

Adam also discusses $D_{\mathop{no3}\ell}(n)$. No nontrivial lower bound is known.

(Throughout, I believe Adam's $D_{\ldots} =$ your $g_{\ldots}$.)

$\endgroup$
1
  • 1
    $\begingroup$ (+1) many thanks for the article! yes my $g$ is same as the usual notation $D$ (I used $g$ 'coz of the wiki article).. I came across the $\textrm{no}3 \ell$ lower bound via a MSE question recently and have been dying to know if there were better bounds ever since. $\endgroup$
    – r9m
    Jun 17, 2015 at 23:15
2
$\begingroup$

There has been recent progress on this problem published in the annals of mathematics:

On the Erdős distinct distances problem in the plane
Pages 155-190 from Volume 181 (2015), Issue 1 by Larry Guth, Nets Hawk Katz

"In this paper, we prove that a set of N points in $\mathbb{R}^2$ has at least $c\frac{N}{\log N}$ distinct distances, thus obtaining the sharp exponent in a problem of Erdős."

$\endgroup$
1
  • $\begingroup$ (+1) Thanks! :-) I found the paper after a few days of asking the question! $\endgroup$
    – r9m
    Oct 18, 2015 at 9:04

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.