Dynamic Stabbing Queries with Sub-logarithmic Local Replacement for Overlapping Regions in R^2.

Abstract

We present an approximation data structure to maintain a set of \emph{fat} regions in $\mathbb{R}^2$ subject to fast insertions and deletions of the regions, stabbing queries, local replacement. Local replacement is a new concept where we replace a region with a region that is "similar" to the original region. We elaborate on earlier result obtained by Löffler, Strash and Simons which shows that it is possible to have a linear size data structure that supports insertions, deletions and stabbing queries in logarithmic time and local replacement in sub-logarithmic time, if the regions are disjoint. We also discuss another earlier result from Löffler and Khramtcova where they present a data structure that supports these operations for overlapping intervals in $\mathbb{R}^1$, where the time bounds for our desired operations depend on the maximum overlap (\emph{ply}) of the intervals. We prove that this approach cannot be extended to $\mathbb{R}^2$ and continue with introducing a data structure that supports approximate queries. Our data structure can support $\epsilon$-approximate stabbing queries, for $\epsilon = \frac{1}{2^m + 1}$ in $\mathcal{O}(m + \log(n))$ time and local replacement in $\mathcal{O}(2^{m}\log(\log(n)))$ time. Lastly we present a theorem that says that no reduction proof from the problem of stabbing queries with sub-logarithmic local replacement in $\mathbb{R}^2$ to binary search can exist. Our approximation bounds show that a logarithmic lower bound for stabbing queries with local replacement is likely, but our results show that proving this lower bound through a reduction to binary search or heap operations is infeasible.