Epsilon-approximations
In this post, we review the technique of $\varepsilon$-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\Gamma$, for some collection of ranges $\Gamma$, we can efficiently count $|P\cap\Gamma|$. It turns out that Problem 1 is very difficult. Efficient (linear space and polyloagrithmic query time) data structures are only possible when $\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 $\varepsilon$, we want to preprocess $P$ into a structure so that for any query ran