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.

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