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

### Gokarna Sharma

### Costas Busch

### Ramachandran Vaidyanathan

### Suresh Rai

### Jerry L. Trahan

*Computational Geometry: Theory and Applications*,
vol. 48, no. 9, pp. 688-702, 2015

#### 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 is
the discrete version of the two-dimensional Klee's measure problem for streaming
inputs. Given epsilon, delta between 0 and 1,
we provide (epsilon, delta)-approximations for bounded side
length rectangles and for bounded aspect ratio rectangles.
For the case of arbitrary rectangles, we provide an
O(sqrt(logU))-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 are polylogarithmic in U. We construct efficient transformation techniques
that project rectangle areas to one-dimensional ranges and then use a streaming
algorithm for the one-dimensional Klee's measure problem to obtain these approximations.
The projections are deterministic, and to our knowledge these are
the first approaches of this kind that provide efficiency and accuracy trade-offs in
the streaming model.