A Simple Streaming Algorithm for Minimum Enclosing Balls
Hamid Zarrabi-Zadeh, Timothy M. Chan · 2006
We analyze an extremely simple approximation algo-rithm for computing the minimum enclosing ball (or the 1-center) of a set of points in high dimensions. We prove that this algorithm computes a 3/2-factor approx-imation in any dimension using minimum space in just one pass over the data points. 1