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 ( d n ) -space data structure that can maintain a 1.22-approximate minimum enclosing ball in O ( d log n ) expected amortized time per insertion/deletion.
dynamic algorithms high dimension streaming algorithms