## ''An Efficient Transformation for the Klee's Measure Problem in the Streaming Model''

### Gokarna Sharma

### Costas Busch

### Ramachandran Vaidyanathan

### Suresh Rai

### Jerry L. Trahan

*Proc. 24th Canadian Conference on Computational Geometry*
pp. 91-96, 2012

#### Abstract:

Given a stream of rectangles over a discrete space, we consider
the problem of computing the total number of distinct
points covered by the rectangles. This can be seen
as the discrete version of the two-dimensional Klee's measure
problem for streaming inputs. We provide an (epsilon, delta)-
approximation for fat rectangles. For the case of arbitrary
rectangles, we provide an O(sqrt{log U})-approximation,
where U is the total number of discrete points in the two-dimensional
space. The time to process each rectangle, the
total required space, and the time to answer a query for
the total area is polylogarithmic in U. Our approximations
are based on an efficient transformation technique which
projects rectangle areas to one-dimensional ranges, and then
uses an F_0 streaming algorithm in the one-dimensional
space. The projection is deterministic and to our knowledge
it is the first approach of this kind which provides efficiency
and accuracy trade-offs in the streaming model.