A Bichromatic Incidence Bound and an Application
We prove a new, tight upper bound on the number of incidences between points and hyperplanes in Euclidean d-space. Given n points, of which k are colored red, there are O (d) (m (2/3) k (2/3) n ((d-2)/3)+kn (d-2)+m) incidences between the k red points and m hyperplanes spanned by all n points provided that m=Omega(n (d-2)). For the monochromatic case k=n, this was proved by Agarwal and Aronov (Discrete Comput. Geom. 7(4):359-369, 1992). We use this incidence bound to prove that a set of n points, no more than n-k of which lie on any plane or two lines, spans Omega(nk (2)) planes. We also provide an infinite family of counterexamples to a conjecture of Purdy's (ErdAs and Purdy in Handbook of Combinatorics, vol. 1, pp. 809-873, Elsevier, Amsterdam, 1995) on the number of hyperplanes spanned by a set of points in dimensions higher than 3, and present new conjectures not subject to the counterexample.
incidence bound hyperplane arrangement