Range searching: what is $\epsilon$?
In some of these bounds, the $\varepsilon$ doesn't come from an approximation, but rather from the degree to which you recurse in a partition tree. Roughly speaking, the idea goes like this. Find a small sample of the input objects that form an arrangement so that the remaining objects are "spread out nicely". In particular, each cell of the arrangement is not intersected by too many of the remaining objects. Then recurse in each piece. 

Using things like $(1/r)$-cuttings, you get recurrences that look like

$$ S(n) = r^d( 1 + S(n/r) ) $$

Solving such recurrences gives you bounds like $S(n) = n^{d+\varepsilon}$, where $\varepsilon$ is roughly $1/\log r$.