## 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