Ramsey-remainder for convex sets and the Erdős–Szekeres theorem Original Research Article

As a consequence of the Erdős–Szekeres theorem we prove that, for n large enough, any set of kn points, in general position in Ed, d⩾3, 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.