Orthogonal Range Reporting and Rectangle Stabbing for Fat Rectangles

Abstract

In this paper we study two geometric data structure problems in the special case when input objects or queries are fat rectangles. We show that in this case a significant improvement compared to the general case can be achieved. We describe data structures that answer two- and three-dimensional orthogonal range reporting queries in the case when the query range is a \emph{fat} rectangle. Our two-dimensional data structure uses $O(n)$ words and supports queries in $O(\log \log U+k)$ time, where $n$ is the number of points in the data structure, $U$ is the size of the universe and $k$ is the number of points in the query range. Our three-dimensional data structure needs $O(n{\log }^{\epsilon }U)$ words of space and answers queries in $O(\log \log U+k)$ time. We also consider the rectangle stabbing problem on a set of three-dimensional fat rectangles. Our data structure uses $O(n)$ space and answers stabbing queries in $O(\log U\log \log U+k)$ time.

extended version of a WADS'19 paper