A Bichromatic Incidence Bound and an Application to Determined Planes
Ben Lund, George Purdy, Justin W. Smith · arXiv (Cornell University) · 2010
We prove that there are O(m 2/3 k 2/3 n (d 2)/3 + kn d 2 ) incidences between k red points and m hyperplanes that are determined jointly by the red points and n k blue points. This is a generalization of an incidence bound proved by Agarwal and Aronov [1] (i.e., when k = n). We provide an explicit construction that attains the asymptotic result, showing that the bound is tight. We apply the new bichromatic incidence bound to establish that a monochromatic set of r points, no more than r s of which lie on any plane or pair of skew lines, determines (rs 2 ) planes. This is a three dimensional analog of the Beck-Erdýos theorem [2] on the number of lines determined by a planar point set. We demonstrate a counterexample to a conjecture of Purdy’s [3], and provide a modified version. We also conjecture a generalization of the Beck-Erdýos theorem to arbitrary dimensions.