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 problem where a lower bound of Ω (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 observation by showing that if the points of S lie on a constant number of convex curves, the number of k-sets remains linear in n.
展开▼
