# 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 short, you should read the bound as "you can make the exponent smaller at the cost of a larger hidden constant in the asymptotic bound". Usually this means that the running time bound is something like $f(\epsilon)m^{1+\epsilon}$ where $f$ goes to infinity as $\epsilon$ goes to 0. You could "get rid" of $\epsilon$ at the cost of a polylog factor if $f$ were of polynomial growth, but sometimes $f$ is exponential or worse, or maybe even bounding $f$ in an explicit way is challenging. – Sasho Nikolov Nov 19 '13 at 1:58
• @Sasho Nikolov, Thanks, I wasn't sure if these particular algorithms were deterministic or were something like $\epsilon$-approximation algorithms. I thought it was probably deterministic (in the way you mentioned), but had found a passing remark in one of Chazelle's papers that some of these are randomized, and then began to second guess myself. :) – John Nov 19 '13 at 14:38
• determinism vs randomization is not quite the issue. you could have the same kind of bound for randomized algorithms (say with constant probability of success). but i am fairly sure the $\epsilon$ is not from approximation and has nothing to do with probability of success or some such parameter. chazelle discusses data structures with very similar bounds for simplex range searching, in his discrepancy method book – Sasho Nikolov Nov 19 '13 at 18:32

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$.