کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
414289 | 680876 | 2014 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Streaming and dynamic algorithms for minimum enclosing balls in high dimensions
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
At SODAʼ10, Agarwal and Sharathkumar presented a streaming algorithm for approximating the minimum enclosing ball of a set of points in d -dimensional Euclidean space. Their algorithm requires one pass, uses O(d)O(d) space, and was shown to have approximation factor at most (1+3)/2+ε≈1.3661. We prove that the same algorithm has approximation factor less than 1.22, which brings us much closer to a (1+2)/2≈1.207 lower bound given by Agarwal and Sharathkumar.We also apply this technique to the dynamic version of the minimum enclosing ball problem (in the non-streaming setting). We give an O(dn)O(dn)-space data structure that can maintain a 1.22-approximate minimum enclosing ball in O(dlogn) expected amortized time per insertion/deletion.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computational Geometry - Volume 47, Issue 2, Part B, February 2014, Pages 240–247
Journal: Computational Geometry - Volume 47, Issue 2, Part B, February 2014, Pages 240–247
نویسندگان
Timothy M. Chan, Vinayak Pathak,