Here are a few thoughts about whether one can get a much better bound by imposing some natural condition on the set of points.

First, observe that the circle example generalizes to points in any convex (or concave) curve. This allows us to show that a random (in a suitable sense) set of points will give rise to a pretty large bound. For example, suppose we choose n points uniformly at random in the unit square. If we form an m-by-m grid of squares, where m is cn^{1/2} for some small positive constant c, then most of the squares in this grid will contain a point. With the help of that observation, one can obtain something like n^{1/4} points (I think) that lie on a convex curve. The way I'd do it is I'd pick a random circle of diameter 1/10 that lies in the square, argue that (on average) it intersects many squares of the grid that contain a point in the original set, and that we can pick a reasonably separate set of these squares. Since the squares have diameter m^{-1} or so, I think we need them to be at least m^{-1/2} apart for points in these squares to be in convex position: hence my suggestion of n^{1/4}.

So that suggests that a typical set of points will give rise to at least exp(cn^{1/4}) legal sets. I haven't checked whether it is easy to improve that bound.

This in turn suggests that the only way of getting a polynomial bound is to choose a rather peculiar set of points. The most obvious general idea for how to do that is some kind of inductive construction. For example, one could iterate the following procedure: given a finite set of points, replace each point by a tiny configuration that consists of the three vertices of a triangle plus a point in the interior of that triangle. Iterating that k times would give 4^k points. I don't know whether that particular construction gets one anywhere, but the thought behind it is to try as hard as possible to force triples of points to contain plenty of other points in their convex hull, or else to belong to small common triangles.

But that's more like a possible approach to constructing some points in general position that give rise to few legal sets rather than an interesting condition that would guarantee this. It seems to me because of the first argument that a set with only a few legal subsets would have to be extremely special and carefully constructed.

of Scontained in the convex hull of B is B? In other words, $B = P \cap S$ for some convex set $P$. If we work in one dimension and let`$S = \{1,2,3\}$`

, then if I understand,`$\{1,2\}, \{2,3\}$`

are legal subsets, but`$\{1,3\}$`

is not. – Nate Eldredge Jun 9 '10 at 22:13