No label defined (Q4464707)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 2068096
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 2068096 |
Statements
27 May 2004
0 references
Erdős-Szekeres theorem
0 references
convex polygon
0 references
Happy End Theorem
0 references
0.8680079
0 references
0.8404602
0 references
0.82869726
0 references
0.82806283
0 references
0.8256246
0 references
0 references
0.82260513
0 references
0.8217752
0 references
0.81982803
0 references
0.81869155
0 references
The classical Erdős-Szekeres convex polygon theorem states that for each \(k\) there is an \(n(k)\) such that any set of \(n(k)\) points in the plane, no three of them on a line, contains \(k\) points that are vertices of a convex \(k\)-gon. This theorem has been generalized in many directions. In this paper, the authors begin by relaxing the `no three points collinear' assumption to `no \(l\) points collinear' or equivalently the convex hull of any two points contains at most \(l\) points. The condition on the admissible sets can then be made stronger again as `the convex hull of any \(k\) points contains at most \(l\) points of the sets. For each \(k,l\) the authors give bounds for the analogue of the Erdős-Szekeres theorem, the minimum number \(f^n_{(k,l)}\) such that any set of \(f^n_{(k,l)}\) points, in which the convex hull of any \(k\) points contains at most \(l\) points, contains the vertices of a convex \(n\)-gon. Sets with a similar restriction with \(k=3\) (each triangle contains at most \(l\) points) have already been studied in the context of the `empty polygon'-variant by \textit{P. Valtr} [Discrete Comput. Geom. 28, No. 4, 671--682 (2002; Zbl 1022.52007)]. For the entire collection see [Zbl 1034.52002].
0 references