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.
Post a Comment