Paper Info
Title
Tight Space Bounds for Two-Dimensional Approximate Range Counting.
Abstract
We study the problem of two-dimensional orthogonal range counting with additive error. Given a set P of n points drawn from an n× n grid and an error parameter ϵ, the goal is to build a data structure, such that for any orthogonal range R, it can return the number of points in P ∩ R with additive error ϵ n. A well-known solution for this problem is obtained by using ϵ-approximation, which is a subset A⊆ P that can estimate the number of points in P ∩ R with the number of points in A ∩ R. It is known that an ϵ-approximation of size O(1/ϵ log 2.5 1/ϵ) exists for any P with respect to orthogonal ranges, and the best lower bound is Ω(1/ϵ log 1/ϵ). The ϵ-approximation is a rather restricted data structure, as we are not allowed to store any information other than the coordinates of the points. In this article, we explore what can be achieved without any restriction on the data structure. We first describe a simple data structure that uses O(1/ϵ(log 21/ϵ + log n)) bits and answers queries with error ϵ n. We then prove a lower bound that any data structure that answers queries with error ϵ n will have to use Ω(1/ϵ (log 21/ϵ + log n)) bits. Our lower bound is information-theoretic: We show that there is a collection of 2Ω(nlog n) point sets with large union combinatorial discrepancy and thus are hard to distinguish unless we use Ω(nlog n) bits.
Year
DOI
Venue
2018
10.1145/3205454
ACM Trans. Algorithms
Keywords
Field
DocType
Data structures, discrepancy theory, range counting
Data structure,Discrete mathematics,Binary logarithm,Combinatorics,Upper and lower bounds,Discrepancy theory,Grid,Mathematics
Journal
Volume
Issue
ISSN
14
2
1549-6325
Citations 
PageRank 
References 
1
0.35
10
Authors
2
Name
Order
Citations
PageRank
Zhewei Wei121520.07
Ke Yi2165977.79