A class of point-sets with few k-sets

A k-set of a finite set S of points in the plane is a subset of cardinality k that can be separated from the rest by a straight line. The question of how many k-sets a set of n points can contain is a long-standing open probl em where a lower bound of Omega (n log k) and an upper bound of O(nk(1/3)) are known today. Under certain restrictions on the set S, for example, if all points lie on a convex curve, the number of k-sets is linear. We generalize this observat ion by showing that if the points of S lie on a constant number of convex c urves, the number of k-sets remains linear in n. (C) 2000 Elsevier Science B.V. All rights reserved.