Orthogonal Range Reporting and Rectangle Stabbing for Fat Rectangles

05/07/2019
by   Timothy M. Chan, et al.
0

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( 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^εU) words of space and answers queries in O( 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( U U +k) time.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset