An optimal extension of the centerpoint theorem

Nabil H. Mustafa; Saurabh Ray

doi:10.1016/j.comgeo.2007.10.004

An optimal extension of the centerpoint theorem

Nabil H. Mustafa, Saurabh Ray

Computer Science

Research output: Contribution to journal › Article › peer-review

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 language	English (US)
Pages (from-to)	505-510
Number of pages	6
Journal	Computational Geometry: Theory and Applications
Volume	42
Issue number	6-7
DOIs	https://doi.org/10.1016/j.comgeo.2007.10.004
State	Published - 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

Access to Document

10.1016/j.comgeo.2007.10.004

Cite this

@article{b5f24aae678e4031b857cc3838ca39f3,

title = "An optimal extension of the centerpoint theorem",

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.",

keywords = "Centerpoint theorem, Combinatorial geometry, Discrete geometry, Extremal methods, Hitting convex sets, Weak -nets",

author = "Mustafa, {Nabil H.} and Saurabh Ray",

year = "2009",

month = aug,

doi = "10.1016/j.comgeo.2007.10.004",

language = "English (US)",

volume = "42",

pages = "505--510",

journal = "Computational Geometry: Theory and Applications",

issn = "0925-7721",

publisher = "Elsevier",

number = "6-7",

}

TY - JOUR

T1 - An optimal extension of the centerpoint theorem

AU - Mustafa, Nabil H.

AU - Ray, Saurabh

PY - 2009/8

Y1 - 2009/8

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

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

KW - Centerpoint theorem

KW - Combinatorial geometry

KW - Discrete geometry

KW - Extremal methods

KW - Hitting convex sets

KW - Weak -nets

UR - http://www.scopus.com/inward/record.url?scp=84867956198&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84867956198&partnerID=8YFLogxK

U2 - 10.1016/j.comgeo.2007.10.004

DO - 10.1016/j.comgeo.2007.10.004

M3 - Article

AN - SCOPUS:84867956198

SN - 0925-7721

VL - 42

SP - 505

EP - 510

JO - Computational Geometry: Theory and Applications

JF - Computational Geometry: Theory and Applications

IS - 6-7

ER -

An optimal extension of the centerpoint theorem

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this