Selection lemmas for various geometric objects (Q2828788)

Selection lemmas are classical results in discrete geometry and have applications in many geometric problems. Selection-lemma-type results typically show that there exists a point that is contained in many objects that are induced (spanned) by an underlying point set.NEWLINENEWLINEThe first selection lemma has been extensively studied for simplices in \(\mathbb{R}^{d}\). However, no previous work is known on the first selection lemma for other geometric objects. In this paper, the first selection lemma for other geometric objects like axis-parallel boxes and balls in \(\mathbb {R}^{d}\) is presented. Two variants are studied: weak and strong. In the weak variant it is assumed that the piercing point \(p \in \mathbb{R}^{d}\). In the strong variant it is, additionally, assumed that \(p \in P\) where \(P\) is the set of points.NEWLINENEWLINEAdditionally, in the second selection lemma, an arbitrary \(m\)-sized subset of the set of all objects induced by \(P\) is considered. For axis-parallel rectangles the lower bound of \(\Omega(\frac{m^{3}}{n^{4}})\) is proved. In other words, it is proved that there exists a point in the plane that is contained in \(\Omega(\frac{m^{3}}{n^{4}})\) rectangles. This result improves the bound known from the literature.