Small Strong Epsilon Nets

2012/08/14 by Pradeesha Ashok, Ashok, Pradeesha, Umair Azmi +3
Computer Science · #Computational Geometry (cs.CG) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #cs.CG #cs.DM

paper · pdf · doi:10.48550/arxiv.1208.2785

19 pages, 12 figures

arxiv created 2012/08/14 · arxiv updated 2012/08/15

Abstract

Let P be a set of n points in ℝ^d. A point x is said to be a centerpoint of P if x is contained in every convex object that contains more than dn\over d+1 points of P. We call a point x a strong centerpoint for a family of objects C if x ∈ P is contained in every object C ∈ C that contains more than a constant fraction of points of P. A strong centerpoint does not exist even for halfspaces in ℝ². We prove that a strong centerpoint exists for axis-parallel boxes in ℝ^d and give exact bounds. We then extend this to small strong ε-nets in the plane and prove upper and lower bounds for ε_i^S where S is the family of axis-parallel rectangles, halfspaces and disks. Here ε_i^S represents the smallest real number in [0,1] such that there exists an ε_i^S-net of size i with respect to S.

Related

• On Strong Centerpoints
• An Improved Bound for Weak Epsilon-Nets in the Plane
• Extending the centerpoint theorem to multiple points
• Stronger Bounds for Weak Epsilon-Nets in Higher Dimensions
• Epsilon-Nets for Halfspaces Revisited