\(k\)-sets and random hulls (Q1316654)

Let \(S\) denote a set of \(n\) points in the plane, no 3 collinear. With \(a\), \(b\in S\) let \(w(a,b)=\) the number of points of \(S\) lying to the right of the line through \(a\) and \(b\) directed from \(a\) to \(b\). Let \(f_ k=f_ k(S)\) denote the number of pairs \((a,b)\) for which \(w(a,b)=k\), and let \(h_ r=h_ r(S)\) denote the expected number of vertices of the convex hull of a random sample of \(r\) points of \textit{S. K. L. Clarkson} and \textit{P. W. Shor} [Discrete Comput. Geom. 4, No. 5, 387-421 (1989; Zbl 0681.68060)] showed that \[ \sum^{n-r}_{j=0} {{n-j-2 \choose r- 2}\over {n \choose r}} f_ j=h_ r, \qquad r=2,3,\ldots,n. \] The author develops and studies similar relationships between the \(f_ k\)'s and the \(h_ r\)'s. Among these are formulas that express each \(f_ k\) as a linear combination of the \(h_ r\)'s, a system of linear relationships between the \(h_ r\)'s that hold for any set of \(n\) points in the plane, formulas for certain sums involving the \(f_ k\)'s and several ``universal'' properties of the sequences \(h_ r\). Also, extensions are made to higher dimensions, to Delaunay triangulations and more. All of this illuminates (but does not solve) the 25 year old problem regarding the number of \(k\)-subsets -- subsets of size \(k\) which can be separated from their complements by a line.