MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question

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.

share|cite|improve this answer
Dear Aaron, thank you for your answer, but do you know, specifically, what is an concrete example of a set of $2^{N-2}$ points so that no $N$ are the vertices of a convex $N$-gon? Thanks! – Diorn Dec 24 '12 at 22:28
No I do not. However I just checked and the construction is just a few lines in It may take more than a few minutes to understand it though. – Aaron Meyerowitz Dec 25 '12 at 5:30
Aaron, I looked into that paper, but in that paper, are $S_{k_i}$ any subsets or subsets in special configurations? Thanks! – Diorn Dec 25 '12 at 7:02
I mean at the top of the 3rd page of that paper. – Diorn Dec 25 '12 at 7:07
I have spent more time with that paper and understand what I did not before: pages 55 and 56 are not there! So seek out a complete copy of the paper. Sorry that I did not notice before. – Aaron Meyerowitz Dec 25 '12 at 9:53

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?

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.