5
$\begingroup$

Orthogonal 2-dimensional range reporting is the problem of storing a set of values from $U \times V$, where $U$ and $V$ are totally ordered universes, subject to queries of the form "Return all stored points in the four-sided box $[a,b] \times [c,d]$", where $a,b \in U$ and $c,d \in V$ are parameters of the query.

Nekrich, in "Orthogonal range searching in linear and almost-linear space ", summarizes the best known results for linear space:

$$ \begin{array}{|l|l|l|} \hline \text{Reference} & \text{Query Time} & \text{Modification Time} \\ \hline \text{Kreveld and Overmars} & O(\sqrt{n \lg n} + k) & O(\lg n)\\ \hline \text{Chazelle} & O((k+1)\lg^2 n) & O(\lg^2 n)\\ \hline \text{Nekrich} & O(\lg n + k \lg^\varepsilon n) & O(\lg^{3+\varepsilon} n) \\ \hline \end{array} $$

What are the best known extensions of these in external memory? The result from Arge et al.'s "On two-dimensional indexability and optimal range search indexing" uses superlinear space. The only generalizations I know have bounds

$$ \begin{array}{|l|l|l|} \hline \text{Reference} & \text{Query Time} & \text{Modification Time} \\ \hline \text{Kanth and Singh} & O(\sqrt{n/B} + k/B) & O(\lg_B n)\\ \hline \text{Procopiuc et al.} & O(\sqrt{n/B} + k/B) & O\left(\frac{1}{B} \left( \lg_{M/B} \frac{n}{B}\right) \left(\lg \frac{n}{M}\right)\right)\\ \hline \end{array} $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.