Ramsey-remainder for convex sets and the Erd?sSzekeres theorem
As a consequence of the Erd?sSzekeres theorem we prove that, for n large enough, any set of kn points, in general position in , can be partitioned into n convex subsets of size k. Although this is far from being true for d=2, we find the exact conditions under which, for sufficiently large n, any set of 4n points, in general position in the plane, can be partitioned into n convex quadrilaterals. Moreover, we design an efficient algorithm which either finds such a partition, or indicates that such a partition does not exist, thus answering a question of Joe Mitchell.
erd?s-szekeres theorem combinatorial convexity ramsey theorem geometric algorithms