## Abstract

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 0 < ∈, δ < 1, we provide (∈, δ)-approximations for bounded side length rectangles and for bounded aspect ratio rectangles. For the case of arbitrary rectangles, we provide an O(Formula presented.)-approximation, where U is the total number of discrete points in the two-dimensional space. The time to process each rectangle and the total required space are polylogarithmic in U. The time to answer a query for the total area is constant. 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.

Original language | English (US) |
---|---|

Article number | 1396 |

Pages (from-to) | 688-702 |

Number of pages | 15 |

Journal | Computational Geometry: Theory and Applications |

Volume | 48 |

Issue number | 9 |

DOIs | |

State | Published - Oct 1 2015 |

Externally published | Yes |

## Keywords

- Bounded aspect ratio rectangles
- Bounded side length rectangles
- Klee's measure problem
- Streaming model
- Transformations

## ASJC Scopus subject areas

- Computer Science Applications
- Geometry and Topology
- Control and Optimization
- Computational Theory and Mathematics
- Computational Mathematics