License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2022.10
URN: urn:nbn:de:0030-drops-160182
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16018/
Go to the corresponding LIPIcs Volume Portal

Balko, Martin ; Scheucher, Manfred ; Valtr, Pavel

Erdős-Szekeres-Type Problems in the Real Projective Plane

pdf-format:
LIPIcs-SoCG-2022-10.pdf (0.9 MB)

Abstract

We consider point sets in the real projective plane ℝ?² and explore variants of classical extremal problems about planar point sets in this setting, with a main focus on Erdős-Szekeres-type problems.
We provide asymptotically tight bounds for a variant of the Erdős-Szekeres theorem about point sets in convex position in ℝ?², which was initiated by Harborth and Möller in 1994. The notion of convex position in ℝ?² agrees with the definition of convex sets introduced by Steinitz in 1913.
For k ≥ 3, an (affine) k-hole in a finite set S ⊆ ℝ² is a set of k points from S in convex position with no point of S in the interior of their convex hull. After introducing a new notion of k-holes for points sets from ℝ?², called projective k-holes, we find arbitrarily large finite sets of points from ℝ?² with no projective 8-holes, providing an analogue of a classical result by Horton from 1983. We also prove that they contain only quadratically many projective k-holes for k ≤ 7. On the other hand, we show that the number of k-holes can be substantially larger in ℝ?² than in ℝ² by constructing, for every k ∈ {3,… ,6}, sets of n points from ℝ² ⊂ ℝ?² with Ω(n^{3-3/5k}) projective k-holes and only O(n²) affine k-holes. Last but not least, we prove several other results, for example about projective holes in random point sets in ℝ?² and about some algorithmic aspects.
The study of extremal problems about point sets in ℝ?² opens a new area of research, which we support by posing several open problems.

BibTeX - Entry

@InProceedings{balko_et_al:LIPIcs.SoCG.2022.10,
  author =	{Balko, Martin and Scheucher, Manfred and Valtr, Pavel},
  title =	{{Erd\H{o}s-Szekeres-Type Problems in the Real Projective Plane}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{10:1--10:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16018},
  URN =		{urn:nbn:de:0030-drops-160182},
  doi =		{10.4230/LIPIcs.SoCG.2022.10},
  annote =	{Keywords: real projective plane, point set, convex position, k-gon, k-hole, Erd\H{o}s-Szekeres theorem, Horton set, random point set}
}

Keywords: real projective plane, point set, convex position, k-gon, k-hole, Erdős-Szekeres theorem, Horton set, random point set
Collection: 38th International Symposium on Computational Geometry (SoCG 2022)
Issue Date: 2022
Date of publication: 01.06.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI