Improving the first selection lemma in ℝ3

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We present new bounds on the first selection lemma in ℝ3. This makes progress on the open problems of Bukh, Matoušek and Nivash [6] and Boros-Füredi [4] for the three-dimensional case, improving the previously best result of Wagner [8]. While our results narrow the gap between the current best lower and upper bounds, they do not settle this question. However, they indicate that it is the current lower-bounds that are not tight, and we conjecture that the lower-bounds can be further improved to match the current upper bound.

Original languageEnglish (US)
Title of host publicationProceedings of the 26th Annual Symposium on Computational Geometry, SCG'10
Pages354-357
Number of pages4
DOIs
StatePublished - 2010
Event26th Annual Symposium on Computational Geometry, SoCG 2010 - Snowbird, UT, United States
Duration: Jun 13 2010Jun 16 2010

Publication series

NameProceedings of the Annual Symposium on Computational Geometry

Other

Other26th Annual Symposium on Computational Geometry, SoCG 2010
CountryUnited States
CitySnowbird, UT
Period6/13/106/16/10

Keywords

  • Centerpoints
  • First selection lemma
  • Hitting simplices
  • Location depth

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics

Fingerprint Dive into the research topics of 'Improving the first selection lemma in ℝ<sup>3</sup>'. Together they form a unique fingerprint.

Cite this