### abstract

- Let S be a set of n points in ]R d, A k-set of S is a subset S' c S such that S' = SNH for some halfspace H and IS'] -- k. The problem of deter- mining tight asymptotic bounds on the maximum number of k-sets is one of the most intriguing open problems in combinatorial geometry. Due to its im- portance in analyzing geometric algorithms [5, 9], the problem has caught the attention of computa- tional geometers as well [3, 7, 8, 14, 16]. A close to optimal solution for the problem remains elusive even in the plane. The best asymptotic upper and lower bounds in the plane are O(nkU3) (see [6]) and n. 2 n(v/iS--~) (see [15]), respectively. In this … *School of Mathematical Sciences, Tel Aviv University, Tel Aviv 69978, Israel and Courant Institute of Mathematical Sciences, New York University, New York, NY 10012, USA; sharirhath.tau.ac.iL Work by Micha Sharir has been supported by NSF Grant CCR-97- 32101, by a grant from the US-Israeli …