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.