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

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
نویسندگان
, ,