2
$\begingroup$

There are N>1 points in a plane. Consider the set of all distances between pairs of the points. Let $n$ be the number of elements of this set. We know that $n \leq {N \choose 2}.$ What is the lower bound estimate on $n$?

For the sake of clearity, if points are $A_1, A_2, \dots, A_N$, and $S = \{d(A_i, A_j)| 1\leq i < j \leq N \}$, then $n = |S|$.

  • 0
    @n0vakovic and the community: I am backing off of this entire issue. Each of the contributions to the site that I have pointed out are indeed interesting pieces of math - I respectfully disagree with n0vakovic but it is not up to me to decide what does or does not belong here.2010-08-12

1 Answers 1

6

You might want to read this article.

The abstract of this article says:

A classical problem in combinatorial geometry is that of determining the minimum number $f(n)$ of different distances determined by $n$ points in the Euclidean plane. In 1952, L. Moser proved that f(n) > \frac{n^{2/3}}{2\cdot3^{1/3}} - 1 and this has remained for 30 years as the best lower bound known for f(n). It is shown that f(n) > cn^{5/7} for some fixed constant c.