On the number of line separations of a finite set in the plane (Q1821352): Difference between revisions

Let S denote a set of n points in \({\mathbb{R}}^ 2\). S'\(\subseteq S\) is called a k-set of S if \(card\quad (S')=k\) and S' and \(S\setminus S'\) can be strictly separated by a straight line. Let \(f_ k(n)\) denote the maximum number of k-sets which can be realized by a set of n points. The authors show that there are constants \(c_ 1,c_ 2>0\), such that \(c_ 1n \log k \leq f_ k(n) = f_{n-k}(n) \leq c_ 2n\sqrt{k}\) for all n,k with \(k\leq n/2.\) The authors remark that this result has been already shown by different methods in the paper of \textit{P. Erdős}, \textit{L. Lovasz}, \textit{A. Simmons} and \textit{E. G. Straus} in Surv. Combin. Theory, Sympos. Colorado State Univ., Colorado 1971, 139-149 (1973; Zbl 0258.05112).