The so-called first selection lemma states the following: given any set P of n points in ℝd, there exists a point in ℝd contained in at least cdnd+1-O(nd) simplices spanned by P, where the constant cd depends on d. We present improved bounds on the first selection lemma in ℝ3. In particular, we prove that c3≥0. 00227, improving the previous best result of c3≥0. 00162 by Wagner (On k-sets and applications. Ph. D. thesis, ETH Zurich, 2003). This makes progress, for the three-dimensional case, on the open problems of Bukh et al. (Stabbing simplices by points and flats. Discrete Comput. Geom., 2010) (where it is proven that c3≤1/44≈0. 00390) and Boros and Füredi (The number of triangles covering the center of an n-set. Geom. Dedic. 17(1):69-77, 1984) (where the two-dimensional case was settled).
- Selection lemma
ASJC Scopus subject areas
- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics