Skip to main content
1 of 2
Aaron Meyerowitz
  • 30.1k
  • 1
  • 48
  • 104

I am going to assume that the points are no three on a line. I think that only makes things harder anyway. It is known that for any $N$ there is a set of $2^{N-2}$ points in the plane so that no $N$ are the vertices of a convex $N$-gon. So there are configurations of 30 points which need at least 5 subsets and of 60 points (and even 63 points) which need at least 9 subsets. We can also be sure that 6 subsets is enough for 30 points and 11 subsets for 60 points.

There is the conjecture that $2^{N-2}+1$ points are enough to force a convex $N$-gon but that is only known for $N=$3,4,5,6. So with 30 points there may be no 7-gons but there will be hexagons until we have used up all but 16 points. Thus we are assured that, even with a greedy strategy, it can't be worse then using 3 hexagons, then a pentagon, a square, and a triangle for a total of 6. If it is also true that any set of 33 points contains the vertices of a convex 7-gon then one gets a bound of 11 subsets for 60 points (4 7-gons, 3 hexagons, a square and then, perhaps, 2 more subsets for the last 4 points.) Even without that conjectured result, we can still say that 11 subsets suffice because we can use 5 hexagons getting down to 30 points left and then we already said that 6 more are enough.

I am assuming that the convex subsets need not have disjoint interiors. I don't think there is an advantage to considering shared vertices. It may be that there are reasons to know that less subsets suffice.

Aaron Meyerowitz
  • 30.1k
  • 1
  • 48
  • 104