NOTE: All bounds in this abstract are off by some log factors.
Given n points in the plane we want a LARGE subset of them
such that all DISTANCES are distinct. How large can such a set be?
We show that there is always a set of size at least Omega(n^{1/3}).
This proof is elementary.
But why stop at distances? Why not ask about Areas? We can! We do!
But one caveat--- if the points are all on the same line then there
will be only one area- 0. So we modify the problem: Given n points
in the plane, we want a large set such that all NON-ZERO areas
are different. We show that there is always a set of size at least
Omega(n^{1/5}). This proof is elementary.
Why just the plane? We extend our results to many dimensions
and to analogs of distances and areas and volumnes.
Our main result is the following: for all a,d with
1 < a < d+2, for all sets of n points in R^d there
is a subset of size Omega(n^{1/(2a-1)d}) such that all
NON-ZERO volumes of a-subsets are distinct.
This proof is NOT elementary. It uses algebraic geometry!
(We will only sketch it.)
Yet, in spirit, it is similar to the elementary proofs stated above.
Joint work with Conlon, Fox, Harris, Ulrich, and Zbarsky.
See arXiv:1401.6734.