کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
414251 | 680861 | 2015 | 15 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Efficient transformations for Klee's measure problem in the streaming model Efficient transformations for Klee's measure problem in the streaming model](/preview/png/414251.png)
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<ϵ,δ<10<ϵ,δ<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(logU)-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.
Journal: Computational Geometry - Volume 48, Issue 9, October 2015, Pages 688–702