Ramsey-remainder for convex sets and the Erdos-Szekeres theorem

As a consequence of the Erdos-Szekeres theorem we prove that, for n large e nough, any set of kn points, in general position in E-d, d greater than or equal to3, can be partitioned into n convex subsets of size k. Although thi s is far from being true for d = 2, we find the exact conditions under whic h, for sufficiently large n, any set of 4n points, in general position in t he plane, can be partitioned into n convex quadrilaterals. Moreover, we des ign an efficient algorithm which either finds such a partition, or indicate s that such a partition does not exist, thus answering a question of Joe Mi tchell. (C) 2001 Elsevier Science B.V. All rights reserved.