کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
414222 680850 2014 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Small strong epsilon nets
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Small strong epsilon nets
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 47, Issue 9, October 2014, Pages 899–909
نویسندگان
, , ,