An optimal generalization of the centerpoint theorem, and its extensions

Nabil Mustafa, Saurabh Ray

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

Abstract

We prove an optimal generalization 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 allconvex objects containingmore than 4n/7 points of P. We further prove that this bound is tight. We get this bound as part of a more general procedure forfinding small number of points hitting convex sets over P, yieldingseveral improvements over previous results.

Original languageEnglish (US)
Title of host publicationProceedings of the Twenty-third Annual Symposium on Computational Geometry, SCG'07
Pages138-141
Number of pages4
DOIs
StatePublished - 2007
Event23rd Annual Symposium on Computational Geometry, SCG'07 - Gyeongju, Korea, Republic of
Duration: Jun 6 2007Jun 8 2007

Publication series

NameProceedings of the Annual Symposium on Computational Geometry

Other

Other23rd Annual Symposium on Computational Geometry, SCG'07
CountryKorea, Republic of
CityGyeongju
Period6/6/076/8/07

Keywords

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

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics

Fingerprint Dive into the research topics of 'An optimal generalization of the centerpoint theorem, and its extensions'. Together they form a unique fingerprint.

Cite this