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
      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

      Identifiers