Open caps and cups in planar point sets (Q2369923): Difference between revisions
From MaRDI portal
Created a new Item |
Set OpenAlex properties. |
||
(4 intermediate revisions by 3 users not shown) | |||
Property / author | |||
Property / author: Pavel Valtr / rank | |||
Property / reviewed by | |||
Property / reviewed by: Jonathan Schaer / rank | |||
Property / author | |||
Property / author: Pavel Valtr / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Jonathan Schaer / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/s00454-006-1286-3 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2121647599 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 03:42, 20 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Open caps and cups in planar point sets |
scientific article |
Statements
Open caps and cups in planar point sets (English)
0 references
21 June 2007
0 references
Erdős and Szekeres proved their classical result, Theorem 1. For any \(n\geq 3\), there exists a (least) integer \(F(n)\) such that any set of at least \(F(n)\) points in general position in the plane contains \(n\) points in convex position, by showing that for any \(k,\ell\geq 2\) there is a (least) integer \(F'(k,\ell)\) such that any configuration of at least \(F'(k,\ell)\) points contains a \(k\)-cap or an \(\ell\)-cup. Here a configuration \(P\) is a finite set of points in general position in the plane such that no two points have the same \(x\)-coordinate; and a \(k\)-cap (resp. \(k\)-cup) is a sequence of \(k\) points \(p_1,\dots, p_k\) with increasing \(x\)-coordinates that are the vertices of a convex \(k\)-gon with all points \(p_2,\dots, p_{k-1}\) lying above (resp. below) the segment \(p_1p_k\). Here the author investigates the related problem of open caps and cups, i.e. caps and cups with no points of the configuration vertically above, resp. below, the polygonal arc \(p_1,\dots, p_k\). He gives double exponential bounds for the minimal size of \(P\).
0 references
Erdős-Szekeres
0 references
(open) caps and cups
0 references