Colloquium
3:00 p.m., Friday (March 2, 2007)
MATX 1100
Csaba D. Toth
MIT
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 dspace. 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
(n1)/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
.4458nO(1).
In threespace, 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 3space, 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).
