On some metric and combinatorial geometric problems (Q1077726)

Most of the problems surveyed are (for obvious reasons) almost as old as the author; almost all are metric and combinatorial, dealing with distances determined by a finite set of points. A sampling of the problems follows. Let \(S\) denote a set of \(n\) points in the plane, \(f(S)\) the number of different distances determined by the (pairs of) points of \(S\), \(g(S)\) the number of times distance 1 is realized, \(f(n)\) the minimum of \(f(S)\) and \(g(n)\) the maximum of \(f(S)\) (max and min taken over all sets \(S\) of \(n\) points). Find \(f(n)\) and \(g(n)\) for small \(n\); find bounds for large \(n\). If \(S\) implements \(f(n)\) (i.e., \(f(S)=f(n))\) must \(S\) have lattice structure? Assuming \(f(S)=o(n)\), must there always be 4 points in \(S\) which determine at most 3 different distances? Suppose \(S\) contains no isosceles triangles; how small can \(f(S)\) be? Assume \(S\) implements \(f(n)\); is it then true that, for every \(k\), \(S\) contains a subset of \(k\) points which implements \(f(k)\)? In particular, must \(S\) contain an equilateral triangle? How many different sets of \(n\) points implement \(f(n)\)? (Two sets are different if they are not related by a similarity transformation.) Let this number be \(r(n)\). \(r(3)=r(5)=1\) while \(r(4)=3\). What about other values? Can one implement \(f(n)\) and \(g(n)\) simultaneously? Certainly yes for small \(n\), but what about all \(n\)? If the points of \(S\) are the vertices of a convex \(n\)-gon, must one of the vertices be such that among the \(n-1\) segments joining it to the others there are at least \([n/2]\) distinct distances? There are many many more problems. Recent progress by Ajtai, Beck, Komlós, Spencer, Szemerédi and others is reported, conjectures are made, prizes are offered. This is another in a series of papers in which the author updates old problems, presents new ones, focuses on directions for new results and continues to influence this area of combinatorics with generosity and ingenuity.