Title: On approximate halfspace range counting and relative epsilon-approximations
Abstract: 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 Rd with relative error ε, and show that relative ε-approximations, combined with the shallow partitioning data structures of Matoušek, yields efficient solutions to this problem. For example, one of our data structures requires linear storage and O(n1+δ) preprocessing time, for any δ>0, and answers a query in time O(ε-γn1-1/⌊ d/2 ⌋ 2b log* n), for any γ > 2/⌊ d/2⌋ the choice of γ and δ affects b and the implied constants. Several variants and extensions are also discussed.