TY - GEN
T1 - Orthogonal range reporting and rectangle stabbing for fat rectangles
AU - Chan, Timothy M.
AU - Nekrich, Yakov
AU - Smid, Michiel
N1 - Publisher Copyright:
© Springer Nature Switzerland AG 2019.
PY - 2019
Y1 - 2019
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85070608424&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85070608424&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-24766-9_21
DO - 10.1007/978-3-030-24766-9_21
M3 - Conference contribution
AN - SCOPUS:85070608424
SN - 9783030247652
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 283
EP - 295
BT - Algorithms and Data Structures - 16th International Symposium, WADS 2019, Proceedings
A2 - Friggstad, Zachary
A2 - Salavatipour, Mohammad R.
A2 - Sack, Jörg-Rüdiger
PB - Springer
T2 - 16th International Symposium on Algorithms and Data Structures, WADS 2019
Y2 - 5 August 2019 through 7 August 2019
ER -