Selection lemmas for various geometric objects

DOI10.1142/S0218195916500047MaRDI QIDQ2828788zbMATH OpenWikidataFDO

Authors Pradeesha Ashok, Sathish Govindarajan, Ninad Rajgopal

Publication date 26 October 2016

Published in International Journal of Computational Geometry \& Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1401.0443

zbMATH Keywords

centerpointfirst selection lemmainduced objectssecond selection lemma

Mathematics Subject Classification ID

Tilings in (n) dimensions (aspects of discrete geometry) (52C22) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: Selection lemmas are classical results in discrete geometry that have been well studied and have applications in many geometric problems like weak epsilon nets and slimming Delaunay triangulations. 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. In the first selection lemma, we consider the set of all the objects induced (spanned) by a point set $P$. This question has been widely explored for simplices in $mathbb{R}^d$, with tight bounds in $mathbb{R}^2$. In our paper, we prove first selection lemma for other classes of geometric objects. We also consider the strong variant of this problem where we add the constraint that the piercing point comes from $P$. We prove an exact result on the strong and the weak variant of the first selection lemma for axis-parallel rectangles, special subclasses of axis-parallel rectangles like quadrants and slabs, disks (for centrally symmetric point sets). We also show non-trivial bounds on the first selection lemma for axis-parallel boxes and hyperspheres in $mathbb{R}^d$. In the second selection lemma, we consider an arbitrary $m$ sized subset of the set of all objects induced by $P$. We study this problem for axis-parallel rectangles and show that there exists an point in the plane that is contained in $frac{m}^{3}24n^4$ rectangles. This is an improvement over the previous bound by Smorodinsky and Sharir when $m$ is almost quadratic.

Review text

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.

Recommendations

• Hitting and Piercing Rectangles Induced by a Point Set
• Hitting simplices with points in \(\mathbb R^{3}\)
• Selecting Heavily Covered Points
• Point Selections and Weak ε-Nets for Convex Hulls
• Improving the first selection lemma in \(\mathbb{R}^3\)

Cites work

• A point in many triangles
• A Theorem on General Measure
• Fixed-orientation equilateral triangle matching of point sets
• Hitting and Piercing Rectangles Induced by a Point Set
• On the Distribution of Values of Angles Determined by Coplanar Points
• Points and triangles in the plane and halving planes in space
• Small weak epsilon-nets

Cited in

(5)

• Upper bounds for stabbing simplices by a line
• Matching points with disks with a common intersection
• scientific article; zbMATH DE number 2103167 (Why is no real title available?)
• Improving the first selection lemma in \(\mathbb{R}^3\)
• Bounds for Pach's selection theorem and for the minimum solid angle in a simplex

This page was built for publication: Selection lemmas for various geometric objects

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2828788)