Are we out of the woods yet?

In this post, we review the technique of $\epsilon$-approximation, which is a very useful tool in computational geometry to design efficient approximation algorithms. Consider the following problem: Problem 1 (Range Counting). Given a set $P$ of $n$ points, we want to preprocess $P$ into a structure so that for any query range $\gamma \in \mathrm{\Gamma }$, for some collection of ranges $\mathrm{\Gamma }$, we can efficiently count $|P\cap \mathrm{\Gamma }|$. It turns out that Problem 1 is very difficult. Efficient (linear space and polyloagrithmic query time)  data structures are only possible when $\mathrm{\Gamma }$ is a collection of orthogonal ranges. Even for the case of halfspaces, the current best near-linear space data structure requires roughly $O(n^{1-1/d})$ query time. So instead, researchers turn to the approximate version of the problem. Problem 2 (Approximate Range Counting).  Given a set $P$ of $n$ points and an error parameter $\epsilon$, we want to preprocess $P$ into a structure so that for any ...