In 2000, Elekes and Rónyai proved the following: Given a real polynomial
f(x,y) and real sets A,B of size n, the number of distinct values of f on
AxB is superlinear in n, unless f=g(h(x)+k(y)) or f=g(h(x)k(y)). One
application from combinatorial geometry is that the number of distinct
distances between two n-point sets on two lines in the plane is
superlinear, unless the lines are parallel or orthogonal.
An open question is how far "superlinear" can be improved in these
statements. I will discuss recent progress on this question, some related
results, and more applications to combinatorial geometry.
Copyright. All Rights Reserved.