8

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?

r9m
  • 810
  • 6
  • 18

2 Answers2

8

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}$.)

Joseph O'Rourke
  • 149,182
  • 34
  • 342
  • 933
  • 1
    (+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. – r9m Jun 17 '15 at 23:15
2

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."

Samuel Reid
  • 1,401