Triangles of unit and distinct areas

Abstract: Given an equivalence relation on finite point configurations, a typical question in extremal discrete geometry asks the maximum size f_d(n) of an equivalence class and the minimum number g_d(n) of distinct equivalence classes determined by n points in d-space. In this talk, the finite point configurations are simplices, and two simplices are considered to be equivalent if they have the same volume. I'll show how incidence bounds, allowable sequences, and the crossing lemma in topological graph theory lead to new upper and lower bounds on f_d(n) and g_d(n) for d=2 and 3.

In the plane, every n points determine at most O(n^{44/19}) = O(n^{2.3158}) unit triangles. This improves earlier bounds of Pach and Sharir from 1992. No better lower bound is known than \Omega(n^2\log \log n), due to Erdös and Purdy from 1971, which is attained on the \sqrt{\log n}\times (n/\sqrt{n}) integer lattice section. Burton, Purdy, and Straus conjectured that every n noncollinear points in the plane determine at least \lfloor (n-1)/2\rfloor distinct triangle areas, which is attained by n points distributed evenly on two parallel lines. Using allowable sequence and linear optimization, one can prove a lower bound of .4458n-O(1).

In three-space, every n points determine at most O(n^{7/2}) tetrahedra of unit volume, and there are point sets that determine at least \Omega(n^3 \log \log{n}). The tetrahedra spanned by n points in 3-space, not all on a plane, have at least \Omega(n) distinct volumes, which is the best possible bound. This answers an old question of Erdös, Purdy, and Straus.

(Joint work with Adrian Dumitrescu.)

Refreshments will be served at 2:45 p.m. (MATX 1115, Math Lounge).