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.
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
9
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.
answered Dec 13, 2012 at 19:38
-
$\begingroup$ 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! $\endgroup$– DiornCommented Dec 24, 2012 at 22:28
-
$\begingroup$ No I do not. However I just checked and the construction is just a few lines in 193.224.79.10/~p_erdos/1960-09.pdf It may take more than a few minutes to understand it though. $\endgroup$ Commented Dec 25, 2012 at 5:30
-
$\begingroup$ Aaron, I looked into that paper, but in that paper, are $S_{k_i}$ any subsets or subsets in special configurations? Thanks! $\endgroup$– DiornCommented Dec 25, 2012 at 7:02
-
$\begingroup$ I mean at the top of the 3rd page of that paper. $\endgroup$– DiornCommented Dec 25, 2012 at 7:07
-
$\begingroup$ 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. $\endgroup$ Commented Dec 25, 2012 at 9:53
$\begingroup$
$\endgroup$
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?
answered Dec 14, 2012 at 1:54