Hitting Simplices with Points in ℝ3

Abdul Basit, Nabil H. Mustafa, Saurabh Ray, Sarfraz Raza

Research output: Contribution to journalArticle

Abstract

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).

Original languageEnglish (US)
Pages (from-to)637-644
Number of pages8
JournalDiscrete and Computational Geometry
Volume44
Issue number3
DOIs
StatePublished - 2010

Keywords

  • Centerpoint
  • Selection lemma
  • Simplex

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Hitting Simplices with Points in ℝ<sup>3</sup>'. Together they form a unique fingerprint.

  • Cite this