Papers Published
Abstract:
Given a point set PR 2, a subset Q P is an -kernel of P if for every slab W containing Q, the (1+)-expansion of W also contains P. We present a data-stream algorithm for maintaining an -kernel of a stream of points in R 2 that uses O(1/ ) space and takes O(log (1/)) amortized time to process each point. This is the first space-optimal data-stream algorithm for this problem. Copyright 2007 ACM.