An optimal extension of the centerpoint theorem

Nabil H. Mustafa, Saurabh Ray

Research output: Contribution to journalArticle

Abstract

We prove an optimal extension of the centerpoint theorem: given a set P of n points in the plane, there exist two points (not necessarily among input points) that hit all convex sets containing more than 47n points of P. We further prove that this bound is tight. We get this bound as part of a more general procedure for finding small number of points hitting convex sets over P, yielding several improvements over previous results.

Original languageEnglish (US)
Pages (from-to)505-510
Number of pages6
JournalComputational Geometry: Theory and Applications
Volume42
Issue number6-7
DOIs
StatePublished - Aug 2009

Keywords

  • Centerpoint theorem
  • Combinatorial geometry
  • Discrete geometry
  • Extremal methods
  • Hitting convex sets
  • Weak -nets

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 'An optimal extension of the centerpoint theorem'. Together they form a unique fingerprint.

  • Cite this