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