TY - GEN

T1 - Adaptive and approximate orthogonal range counting

AU - Chan, Timothy M.

AU - Wilkinson, Bryan T.

PY - 2013/4/16

Y1 - 2013/4/16

N2 - We present three new results on one of the most basic problems in geometric data structures, 2-D orthogonal range counting. All the results are in the w-bit word RAM model. • It is well known that there are linear-space data structures for 2-D orthogonal range counting with worst-case optimal query time O(logw n). We give an O(n log log n)-space adaptive data structure that improves the query time to O(log log n + logw, k), where k is the output count. When k = O(1), our bounds match the state of the art for the 2-D orthogonal range emptiness problem [Chan, Larsen, and Pǎtraş cu, SoCG 2011]. • We give an O(n log log n)-space data structure for approximate 2-D orthogonal range counting that can compute a (1 + δ)-factor approximation to the count in O(log log n) time for any fixed constant δ > 0. Again, our bounds match the state of the art for the 2-D orthogonal range emptiness problem. • Lastly, we consider the 1-D range selection problem, where a query in an array involves finding the kth least element in a given subarray. This problem is closely related to 2-D 3-sided orthogonal range counting. Recently, Jørgensen and Larsen [SODA 2011] presented a linear-space adaptive data structure with query time O(log log n + logw k). We give a new linear-space structure that improves the query time to O(1 + logw k), exactly matching the lower bound proved by Jørgensen and Larsen.

AB - We present three new results on one of the most basic problems in geometric data structures, 2-D orthogonal range counting. All the results are in the w-bit word RAM model. • It is well known that there are linear-space data structures for 2-D orthogonal range counting with worst-case optimal query time O(logw n). We give an O(n log log n)-space adaptive data structure that improves the query time to O(log log n + logw, k), where k is the output count. When k = O(1), our bounds match the state of the art for the 2-D orthogonal range emptiness problem [Chan, Larsen, and Pǎtraş cu, SoCG 2011]. • We give an O(n log log n)-space data structure for approximate 2-D orthogonal range counting that can compute a (1 + δ)-factor approximation to the count in O(log log n) time for any fixed constant δ > 0. Again, our bounds match the state of the art for the 2-D orthogonal range emptiness problem. • Lastly, we consider the 1-D range selection problem, where a query in an array involves finding the kth least element in a given subarray. This problem is closely related to 2-D 3-sided orthogonal range counting. Recently, Jørgensen and Larsen [SODA 2011] presented a linear-space adaptive data structure with query time O(log log n + logw k). We give a new linear-space structure that improves the query time to O(1 + logw k), exactly matching the lower bound proved by Jørgensen and Larsen.

UR - http://www.scopus.com/inward/record.url?scp=84876032316&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84876032316&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84876032316

SN - 9781611972511

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 241

EP - 251

BT - Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013

T2 - 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013

Y2 - 6 January 2013 through 8 January 2013

ER -