Range searching: what is $\epsilon$? I am interested in range searching purely as a black box in another problem. One problem in particular is that of shooting 2D rays among 2D segments. It seems that Agarwal and Matousek have a well known method for doing this in [1] which requires $O(m^{1 + \epsilon})$ time preprocessing and space to answer ray shooting queries for any fixed positive $\epsilon$. It is not clear to me yet (having read the introduction and conclusion of the paper and skimmed the rest), whether this $\epsilon$ arises due to randomization, approximation, or something else. As I said I only need this as a black box and am somewhat trying to avoid becoming an expert in range searching just to know the answer, and since my initial skimming of the paper didn't produce results I decided to ask it here: which of these three is the algorithm: deterministic, approximate, or randomized? If not deterministic, what is the best that can be done deterministically? 

[1] Agarwal P. K, Matousek, J. Ray shooting and parametric search. STOC '92 Proc. of the 24th annual ACM symp. on Theory of computing. Pages 517-526
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$.