Centerpoints and tverberg's technique

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

Research output: Contribution to journalArticlepeer-review

Abstract

Using a technique that Tverberg and Vrecica (1993) [16] discovered to give a surprisingly simple proof of Tverberg?s theorem, we show the following extension of the centerpoint theorem. Given any set P of n points in the plane, and a parameter 1/3 ≤ c ≤ 1, one can always find a disk D such that any closed half-space containing D contains at least cn points of P. Furthermore, D contains at most (3c ? 1)n/2 points of P (the case c = 1 is trivial ? take any D containing P; the case c = 1/3 is the centerpoint theorem). We also show that, for all c, this bound is tight up to a constant factor. We extend the upper bound to Rd. Specifically, we show that given any set P of n points, one can find a ball D containing at most ((d + 1)c ? 1)n/d points of P such that any half-space containing D contains at least cn points of P.

Original languageEnglish (US)
Pages (from-to)593-600
Number of pages8
JournalComputational Geometry: Theory and Applications
Volume43
Issue number6-7
DOIs
StatePublished - Aug 2010

Keywords

  • Centerdisks
  • Centerpoint theorem
  • Data depth
  • Discrete geometry
  • Tverberg's theorem

ASJC Scopus subject areas

  • Computer Science Applications
  • Geometry and Topology
  • Control and Optimization
  • Computational Theory and Mathematics
  • Computational Mathematics

Fingerprint Dive into the research topics of 'Centerpoints and tverberg's technique'. Together they form a unique fingerprint.

Cite this