Efficient transformations for Klee's measure problem in the streaming model (Q904110): Difference between revisions

The two-dimensional Klee's measure problem is to compute the area of the union of a given set of axis-aligned rectangles. The authors study a variation of this problem, which they refer to as discrete Klee's measure problem with streaming inputs (KMP-SD). To be more precise, let \(\mathbb{Z}_n=\{ 0,1,\dots, 2^n-1\}\) (for some \(n\geq 0\)) and let \(Y=\{ x_0, x_1, \dots, x_{m-1} \}\) be a set of \(m\) rectangles in \(\mathbb{Z}_n \times \mathbb{Z}_n\). That is, each \(x_i\) is a subset of rectangular shape of \(\mathbb{Z}_n \times \mathbb{Z}_n\). The KMP-SD asks to determine the quantity \[ A_m= \left | \bigcup_{i=0}^{m-1} x_i \right | \] for streaming inputs \(x_i\). The authors point out that the optimal algorithmic solution for the classical (non-streaming) problem has a very large workspace requirement, which is too large in the context of streaming applications. While this optimal solution is deterministic and exact, recent work has focused on approximate solutions of the problem reducing workspace and time. The main contributions of the paper are randomized approximation algorithms for the KMP-SD based on two particular deterministic transformations of the input called side-length-map and aspect-ratio-map. These procedures transform the input rectangles into one-dimensional ranges, such that any so called online range-efficient algorithm can be applied to these ranges to solve the KMP-SD.