MIT Combinatorics Seminar

Point-Hyperplane Incidence Bounds And Applications

Csaba David Toth (Massachusetts Institute of Technology)

Wednesday, September 21, 2005   4:30 pm    Room 2-142


The celebrated Szemeredi-Trotter Theorem gives an asymptotically tight bound for the number of incident point-line pairs among n points and m lines in the Euclidean plane. No nontrivial tight bound is known in general for the incidences of points and any other type of curves or surfaces in the Euclidean space. All hyperplanes may be incident to all points in a degenerate configuration where the points are collinear. It turns out that one can give a tight incidence bound if we disregard all degenerate and close-to-degenerate hyperplanes. The new incidence bound has several applications involving distance sets, minimum volume simplices, and point-line configurations in 3D.