On approximate halfspace range counting and relative epsilon-approximations

The paper consists of two major parts. In the first part, we re-examine relative ε-approximations, previously studied in [12, 13, 18, 25], and their relation to certain geometric problems, most notably to approximate range counting. We give a simple constructive proof of their existence in general range spaces with finite VC dimension, and of a sharp bound on their size, close to the best known one. We then give a construction of smaller-size relative ε-approximations for range spaces that involve points and halfspaces in two and higher dimensions. The planar construction is based on a new structure—spanning trees with small relative crossing number, which we believe to be of independent interest. In the second part, we consider the approximate halfspace range-counting problem in R d with relative error ε, and show that relative ε-approximations, combined with the shallow partitioning data structures of Matouˇsek, yields efficient solutions to this problem. For example, one of our data structures requires linear storage and O(n 1+δ) preprocessing time, for any δ> 0, and answers a query in time O(ε −γ n 1−1/⌊d/2 ⌋ 2 b log ∗ n), for any γ> 2/⌊d/2⌋; the choice of γ and δ affects b and the implied constants. Several variants and extensions are also discussed