Upper bound for the number of subsets of N points which exhaust their convex hull Hello.
Looking at a set S of N points in the plane, I call a subset B of S "legal" if the set of points contained in the convex hull of B is exactly B itself. In other words, a subset B of S in legal if there exists some polygon P such that the set of points in and on P is exactly B.
Given N, can you bound from above the number of legal subsets of a set of N points in the plane?
Refinement: Given N, can you bound from above the number of legal subsets of size K of a set of N points in the plane?
Thank you very much.
 A: 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.
A: For the lower bound, I am guessing that every set of N points in the plane contains at least N-1 legal subsets, with equality if and only if the points are in a line.  
A: Why can't you just put the points in a circle? Doesn't that make all subsets legal?
A: If I understand the question, you want the best (i.e. larger) constant $L_k(n)$ such that any set S of $n$ points in the plane (more generally, in a linear space V) always has at least  $L_k(n)$ legal k-subsets. If so, I'd say that $L_k(n)=N-k+1.$ Indeed, if V is a line, we always have equality. In the general case, map linearly and injectively S onto a subset S' of a line. The image of an illegal k-subset of S is still an illegal k-subset of S', showing that there are at least as many legal k-sets in S as there are in S'. The total number is of course at least N(N+1)/2, with equality in dimension 1. 
