
We consider point sets in the real projective plane $\mathbb{R}P^2$ 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 $\mathbb{R}P^2$, which was initiated by Harborth and Möller in 1994. The notion of convex position in $\mathbb{R}P^2$ agrees with the definition of convex sets introduced by Steinitz in 1913. For $k \geq 3$, an (\affine) $k$-hole in a finite set $S \subseteq \mathbb{R}^2$ 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 $\mathbb{R}P^2$, called projective $k$-holes, we find arbitrarily large finite sets of points from $\mathbb{R}P^2$ with no \projective 8-holes, providing an analogue of a classical planar construction by Horton from 1983. We also prove that they contain only quadratically many \projective $k$-holes for $k \leq 7$. On the other hand, we show that the number of $k$-holes can be substantially larger in~$\mathbb{R}P^2$ than in $\mathbb{R}^2$ by constructing, for every $k \in \{3,\dots,6\}$, sets of $n$ points from $\mathbb{R}^2 \subset \mathbb{R}P^2$ with $Ω(n^{3-3/5k})$ \projective $k$-holes and only $O(n^2)$ \affine $k$-holes. Last but not least, we prove several other results, for example about projective holes in random point sets in $\mathbb{R}P^2$ and about some algorithmic aspects. The study of extremal problems about point sets in $\mathbb{R}P^2$ opens a new area of research, which we support by posing several open problems.
The extended abstract appeared at the 38th International Symposium on Computational Geometry (SoCG 2022)
Computational Geometry (cs.CG), FOS: Computer and information sciences, Theory of computation → Computational geometry, hole, Erdős problems and related topics of discrete geometry, 510, k-gon, Planar arrangements of lines and pseudolines (aspects of discrete geometry), FOS: Mathematics, random point set, projective plane, Erdős-Szekeres theorem, Horton set, real projective plane, Information systems → Data structures, Erdős-Szekeres-type problems, Mathematics of computing → Combinatorics, Arrangements of points, flats, hyperplanes (aspects of discrete geometry), 004, convex position, k-hole, point set, Theory of computation → Randomness, geometry and discrete structures, Mathematics of computing → Probability and statistics, Combinatorics (math.CO), ddc: ddc:004
Computational Geometry (cs.CG), FOS: Computer and information sciences, Theory of computation → Computational geometry, hole, Erdős problems and related topics of discrete geometry, 510, k-gon, Planar arrangements of lines and pseudolines (aspects of discrete geometry), FOS: Mathematics, random point set, projective plane, Erdős-Szekeres theorem, Horton set, real projective plane, Information systems → Data structures, Erdős-Szekeres-type problems, Mathematics of computing → Combinatorics, Arrangements of points, flats, hyperplanes (aspects of discrete geometry), 004, convex position, k-hole, point set, Theory of computation → Randomness, geometry and discrete structures, Mathematics of computing → Probability and statistics, Combinatorics (math.CO), ddc: ddc:004
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
