کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
414222 | 680850 | 2014 | 11 صفحه PDF | دانلود رایگان |

Let P be a set of n points in RdRd. A point x is said to be a centerpoint of P if x is contained in every convex object that contains more than dnd+1 points of P. We call a point x a strong centerpoint for a family of objects CC if x∈Px∈P is contained in every object C∈CC∈C that contains more than a constant fraction of points of P . A strong centerpoint does not exist even for halfspaces in R2R2. We prove that a strong centerpoint exists for axis-parallel boxes in RdRd and give exact bounds. We then extend this to small strong ϵ -nets in the plane. Let ϵiS represent the smallest real number in [0,1][0,1] such that there exists an ϵiS-net of size i with respect to SS. We prove upper and lower bounds for ϵiS where SS is the family of axis-parallel rectangles, halfspaces and disks.
Journal: Computational Geometry - Volume 47, Issue 9, October 2014, Pages 899–909