Let us generalize this problem to r sets and dimension d:

We have r(d+1) -1 points on the plane. We want to show that we can divide them into r-1 sets of d+1 points and one set of d-2 such that the intersection of the convex hulls of all r sets is not empty.

We take (r-1)*(d+1) +1 of the points and apply Tverberg’s theorem.

It gives us r disjoint nonempty sets which together contain all (r-1)*(d+1) +1 points. The intersection of the convex hulls of these sets is nonempty. Let one of the points in the intersection of the convex hulls be x.

If any of the r sets are bigger than d+1 then by Caratheodory’s theorem there is a d+1 subset that contains x. We take that as the new set in place of the old set and add the additional points to sets less than d+1 making sure none of the additions causes a set to be greater than d+1. We repeat this process untill all of the sets are three or less. Then we add the remaining d-1 points to a sets with d points or less again making sure no set goes over d+1. The result is (r)*(d+1) +1 points divided into r sets of d+1 or less. The only way to do this is r-1 sets of d+1 and one set of d points which gives the desired theorem.

We can add more points and keep the distribution even since adding a point to a set of points increases the convex hull so the intersection of convex hulls still contains x. So we have the following if we have r(d+1) -1 points or more we can divide them into r nonempty sets, the size of each set differing by at most one element from each other set such that the intersection of the convex hulls of the sets is nonempty.

### Like this:

Like Loading...

*Related*

This entry was posted on October 10, 2009 at 4:54 pm and is filed under Uncategorized. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

## Leave a Reply