  In this paper, we prove that a set of $N$ points in ${\bf R}^2$ has at least
$c{N \over \log N}$ distinct distances, thus obtaining the sharp exponent in a
problem of Erd\"os. We follow the set-up of Elekes and Sharir which, in the
spirit of the Erlangen program, allows us to study the problem in the group of
rigid motions of the plane. This converts the problem to one of point-line
incidences in space. We introduce two new ideas in our proof. In order to
control points where many lines are incident, we create a cell decompostion
using the polynomial ham sandwich theorem. This creates a dichotomy: either
most of the points are in the interiors of the cells, in which case we
immediately get sharp results, or alternatively the points lie on the walls of
the cells, in which case they are in the zero set of a polynomial of
suprisingly low degree, and we may apply the algebraic method. In order to
control points where only two lines are incident, we use the flecnode
polynomial of the Rev. George Salmon to conclude that most of the lines lie on
a ruled surface. Then we use the geometry of ruled surfaces to complete the
proof.
