Abstract
Given a positive real parameter ε, we consider the problem of maintaining an ε-approximate Voronoi cell of a fixed point p with respect to a stream S of points in d dimensions. More precisely, we show how to maintain a subset of S , such that the convex polytope induced by the intersection of bisector halfspaces between p and points in this subset is an ε-approximate Voronoi cell. Our algorithm uses Ο(1/ε^(d-1)/2log(1/ε)) storage and O(1/ε^(d-1)/2) time per insertion. This significantly improves existing results under the data stream model. Our result is optimal in space up to a logarithmic factor and matches the best known result in the traditional static model.