کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
414843 | 681058 | 2010 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Reprint of: Weak ϵ-nets have basis of size O(1/ϵlog(1/ϵ)) in any dimension
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
Given a set P of n points in Rd and ϵ>0, we consider the problem of constructing weak ϵ-nets for P. We show the following: pick a random sample Q of size O(1/ϵlog(1/ϵ)) from P. Then, with constant probability, a weak ϵ-net of P can be constructed from only the points of Q. This shows that weak ϵ-nets in Rd can be computed from a subset of P of size O(1/ϵlog(1/ϵ)) with only the constant of proportionality depending on the dimension, unlike all previous work where the size of the subset had the dimension in the exponent of 1/ϵ. However, our final weak ϵ-nets still have a large size (with the dimension appearing in the exponent of 1/ϵ).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 43, Issues 6–7, August 2010, Pages 565-571
Journal: Computational Geometry - Volume 43, Issues 6–7, August 2010, Pages 565-571