Streaming and dynamic algorithms for minimum enclosing balls in high dimensions

Timothy M. Chan, Vinayak Pathak

Research output: Contribution to journalArticlepeer-review

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 languageEnglish (US)
Pages (from-to)240-247
Number of pages8
JournalComputational Geometry: Theory and Applications
Volume47
Issue number2 PART A
DOIs
StatePublished - 2014
Externally publishedYes

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

Fingerprint

Dive into the research topics of 'Streaming and dynamic algorithms for minimum enclosing balls in high dimensions'. Together they form a unique fingerprint.

Cite this