Two theorems on point-flat incidences (Q827305)

Let \(P \subseteq {\mathbb R}^d\) be a set of \(n\) points. According to \textit{E. Szemerédi} and \textit{W. T. Trotter jun.} [Combinatorica 3, 381--392 (1983; Zbl 0541.05012)], for every \(r>1\) the number of lines containing at least \(r\) points from \(P\) is bounded above by \(O(n^2 r^{-3} + n r^{-1})\). Extending a result of \textit{G. Elekes} and \textit{C. D. Tóth} [in: Proceedings of the 21st annual symposium on computational geometry, SCG 2005, Pisa, Italy, June 6--8, 2005. New York, NY: Association for Computing Machinery (ACM). 16--21 (2005; Zbl 1387.52039)], the author obtains a similar upper bound for the number of \(k\)-flats (i.e.\ \(k\)-dimensional affine subspaces) \(\Gamma\) such that \(|\Gamma \cap P| \ge r\) and at most \(\alpha |\Gamma \cap P|\) points of \(P\) lie on any \((k-1)\)-flat contained in \(\Gamma\), where \(0<\alpha<1\). Moreover, the author improves a result of \textit{J. Beck} [Combinatorica 3, 281--297 (1983; Zbl 0533.52004)], as follows: For any integer \(k\ge 1\) and any \(c_k < 1/2\) there is a constant \(c_k'\) such that either \(c_k n\) points of \(P\) are contained in a single \(k\)-flat, or \(P\) spans \(c_k' n^{k+1}\) \(k\)-flats.