Width of points in the streaming model
Alexandr Andoni, Huy Tan Nguyen · Symposium on Discrete Algorithms · 2012
In this article, we show how to compute the width of a dynamic set of low-dimensional points in the streaming model. In particular, we assume that the stream contains both insertions of points and deletions of points to a set S, and the goal is to compute the width of the set S, namely the minimal distance between two parallel hyperplanes sandwiching the point set S.Our algorithm (1 p e) approximates the width of the set S using space polylogarithmic in the size of S and the aspect ratio of S. This is the first such algorithm that supports both insertions and deletions of points to the set S: previous algorithms for approximating the width of a point set only supported additions [Agarwal et al. 2004; Chan 2006], or a sliding window [Chan and Sadjad 2006].This solves an open question from the “2009 Kanpur list” of open problems in data streams, property testing, and related topics [Indyk et al. 2011].