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
    Commented 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
    Commented Oct 18, 2015 at 9:04

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .