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 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(nlog ε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 Ulog log U+ k) time.
Lecture Notes in Computer Science
Computational Geometry Lab

Chan, T.M. (Timothy M.), Nekrich, Y. (Yakov), & Smid, M. (2019). Orthogonal range reporting and rectangle stabbing for fat rectangles. In Lecture Notes in Computer Science. doi:10.1007/978-3-030-24766-9_21