On the number of line separations of a finite set in the plane

Let S denote a set of n points in the Euclidean plane. A subset S′ of S is termed a k-set of S if it contains k points and there exists a straight line which has no point of S on it and separates S′ from S?S′. We let f_k(n) denote the maximum number of k-sets which can be realized by a set of n points. This paper studies the asymptotic behaviour of f_k(n) as this function has applications to a number of problems in computational geometry. A lower and an upper bound on f_k(n) is established. Both are nontrivial and improve bounds known before. In particular, $\text{f}{}_{\mathrm{k}}\text{(n) = f}{}_{\mathrm{n?k}}\text{(n) = Ω(n}\text{log}\text{k)}$ is shown by exhibiting special point-sets which realize that many k-sets. In addition, $\text{f}{}_{\mathrm{k}}\text{(n) = f}{}_{\mathrm{n?k}}\text{(n) = O(nk}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}\text{)}$ is proved by the study of a combinatorial problem which is of interest in its own right.