The number of small semispaces of a finite set of points in the plane (Q1070228)

Let S be a finite set of points in the plane. The intersection of S with a half plane is called a semispace of S, and a semispace of S of cardinality k is called a k-set of S. Let \(f_ k(S)\) denote the number of k-sets of S and put \(g_ k(S)=\sum^{k}_{i=1}f_ i(S).\) Finally, define \(g_{k,n}\) by \(g_{k,n}=\max \{g_ k(S):| S| =n\}.\) Since \(g_{k,n}=g_{n-k,n}\), attention may be restricted to the case \(k\leq n/2\). \textit{J. E. Goodman} and \textit{R. Pollack} [J. Comb. Theory, Ser. A 36, 101-104 (1984; Zbl 0523.51003)] found that \(g_{k,n}\leq 2nk- 2k^ 2-k\) if \(k<n/2\). The present authors show that \(g_{k,n}=kn\) for \(k<n/2\). They give a combinatorial proof based on the ideas of Goodman and Pollack and a geometric proof.