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.



Upper bound for the number of subsets of N points which exhaust their convex hull
Why can't you just put the points in a circle? Doesn't that make all subsets legal?


