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

详细信息    查看全文

• 作者：Ká ; rolyi ; Gyula
• 关键词：Erd&odblac ; s-Szekeres theorem ; Combinatorial convexity ; Ramsey theorem ; Geometric algorithms
• 刊名：Discrete Applied Mathematics
• 出版年：2001
• 出版时间：April 15, 2001
• 年：2001
• 卷：109
• 期：1-2
• 页码：163-175
• 全文大小：158 K

文摘

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 E^d,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.