Abstract
At SODAE10, 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) 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)-space data structure that can maintain a 1.22-approximate minimum enclosing ball in O(dlogn) expected amortized time per insertion/deletion.
Original language | English (US) |
---|---|
Pages (from-to) | 240-247 |
Number of pages | 8 |
Journal | Computational Geometry: Theory and Applications |
Volume | 47 |
Issue number | 2 PART A |
DOIs | |
State | Published - 2014 |
Externally published | Yes |
Keywords
- Dynamic algorithms
- High dimension
- Streaming algorithms
ASJC Scopus subject areas
- Computer Science Applications
- Geometry and Topology
- Control and Optimization
- Computational Theory and Mathematics
- Computational Mathematics