''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


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.