Question

Given any $30$ points in the plane, what is the smallest number of subsets in a subdivision of the set of $30$ points into subsets such that all the points in each subset are on the boundary of the convex hull of the subset? and how about $60$ points? Thanks a lot.

Answer 1

I am going to assume that the points are no three on a line. I think that only makes things harder anyway.

For 30 points (or even 25) 5 subsets can be required. I don't know if 5 subsets are always sufficient, but 6 are. For 60 points (or even 57) 9 subsets can be required however 11 are sufficient for any configuration of 60 points.

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 discard 7 points from a heptagon free set of 32 to get 25 points with no convex heptagons. Similarly, discard 7 points from 64 to get a set of 57 points with no convex octagons.

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 heptagons 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 heptagon, 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.

Answer 2

Consider the general problem of $n$ points (no three on a line). It is known that some $N$ of these points are in convex position if $n=4^N$. Thus for $n$ points we can find $\log_4 n$ points in convex position. After removing them, we can find $\log_4(n-\log_4 n)$ points in convex position, etc. It takes about $n/(\log n)$ steps (does someone know a more accurate estimate?) to remove all the points by this procedure, so we get an upper bound on the number of subsets which is on the order of $n/(\log n)$. Can this be improved?