Ramsey-remainder for convex sets and the Erdős-Szekeres theorem (Q5929326)

In connection with the Erdős-Szekeres theorem is proved that for \(n\) large enough, any set of \(kn\) points, in general position in \(d\)-dimensional Euclidean space, \(d\geq 3\), can be partitioned into \(n\) convex \(k\)-sets (i.e. subsets of size \(k)\). A main part of this paper is the investigation of corresponding problems in the plane \((d=2)\). The author shows: Any set \(P\) of \(4n\) points (in general position in the plane) can be partitioned into \(n\) pairwise (vertex-) disjoint convex quadrilaterals \(C_1,\dots,C_n\) such that \(P= \bigcup^n_{i=1} C_i\). There is no partition \(P=A\cup^*B\) such that \(|A|\) is odd and \(|A\cap C|\) is even for every convex quadrilateral \(C\subset P\). From this results also a complete geometric characterization of the sets that do not satisfy this partition-condition. Based on all these considerations an \(O(n\log n)\) time algorithm is designed which either finds such a partition, or indicates that such a partition does not exist.