Adaptive and approximate orthogonal range counting

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review

Standard

Adaptive and approximate orthogonal range counting. / Chan, Timothy M.; Wilkinson, Bryan T.

In: ACM Transactions on Algorithms, Vol. 12, No. 4, 45, 2016, p. 45:1-45:15.

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review

Harvard

Chan, TM & Wilkinson, BT 2016, 'Adaptive and approximate orthogonal range counting', ACM Transactions on Algorithms, vol. 12, no. 4, 45, pp. 45:1-45:15. https://doi.org/10.1145/2830567

APA

Chan, T. M., & Wilkinson, B. T. (2016). Adaptive and approximate orthogonal range counting. ACM Transactions on Algorithms, 12(4), 45:1-45:15. [45]. https://doi.org/10.1145/2830567

CBE

Chan TM, Wilkinson BT. 2016. Adaptive and approximate orthogonal range counting. ACM Transactions on Algorithms. 12(4):45:1-45:15. https://doi.org/10.1145/2830567

MLA

Chan, Timothy M. and Bryan T. Wilkinson. "Adaptive and approximate orthogonal range counting". ACM Transactions on Algorithms. 2016, 12(4). 45:1-45:15. https://doi.org/10.1145/2830567

Vancouver

Chan TM, Wilkinson BT. Adaptive and approximate orthogonal range counting. ACM Transactions on Algorithms. 2016;12(4):45:1-45:15. 45. https://doi.org/10.1145/2830567

Author

Chan, Timothy M. ; Wilkinson, Bryan T. / Adaptive and approximate orthogonal range counting. In: ACM Transactions on Algorithms. 2016 ; Vol. 12, No. 4. pp. 45:1-45:15.

Bibtex

@article{30aacf4876ad41e78a30b9fe607fbfa7,
title = "Adaptive and approximate orthogonal range counting",
abstract = "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 worstcase optimal query time O(log n/ log log n). We give an O(nlog log n)-space adaptive data structure that improves the query time to O(log log n+ log k/ log log n), 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 et al., 2011]. -We give an O(nlog log n)-space data structure for approximate 2-D orthogonal range counting that can compute a (1+d)-factor approximation to the count in O(log log n) time for any fixed constant d > 0. Again, our bounds match the state of the art for the 2-D orthogonal range emptiness problem. -Last, 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{\o}rgensen and Larsen [2011] presented a linear-space adaptive data structure with query time O(log log n+ log k/ log log n). We give a new linear-space structure that improves the query time to O(1 + log k/ log log n), exactly matching the lower bound proved by J{\o}rgensen and Larsen.",
keywords = "Adaptive, Approximate, Computational geometry, Data structure, Orthogonal, Range counting, Word RAM",
author = "Chan, {Timothy M.} and Wilkinson, {Bryan T.}",
year = "2016",
doi = "10.1145/2830567",
language = "English",
volume = "12",
pages = "45:1--45:15",
journal = "A C M Transactions on Algorithms",
issn = "1549-6325",
publisher = "Association for Computing Machinery, Inc.",
number = "4",

}

RIS

TY - JOUR

T1 - Adaptive and approximate orthogonal range counting

AU - Chan, Timothy M.

AU - Wilkinson, Bryan T.

PY - 2016

Y1 - 2016

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 worstcase optimal query time O(log n/ log log n). We give an O(nlog log n)-space adaptive data structure that improves the query time to O(log log n+ log k/ log log n), 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 et al., 2011]. -We give an O(nlog log n)-space data structure for approximate 2-D orthogonal range counting that can compute a (1+d)-factor approximation to the count in O(log log n) time for any fixed constant d > 0. Again, our bounds match the state of the art for the 2-D orthogonal range emptiness problem. -Last, 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 [2011] presented a linear-space adaptive data structure with query time O(log log n+ log k/ log log n). We give a new linear-space structure that improves the query time to O(1 + log k/ log log n), 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 worstcase optimal query time O(log n/ log log n). We give an O(nlog log n)-space adaptive data structure that improves the query time to O(log log n+ log k/ log log n), 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 et al., 2011]. -We give an O(nlog log n)-space data structure for approximate 2-D orthogonal range counting that can compute a (1+d)-factor approximation to the count in O(log log n) time for any fixed constant d > 0. Again, our bounds match the state of the art for the 2-D orthogonal range emptiness problem. -Last, 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 [2011] presented a linear-space adaptive data structure with query time O(log log n+ log k/ log log n). We give a new linear-space structure that improves the query time to O(1 + log k/ log log n), exactly matching the lower bound proved by Jørgensen and Larsen.

KW - Adaptive

KW - Approximate

KW - Computational geometry

KW - Data structure

KW - Orthogonal

KW - Range counting

KW - Word RAM

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

U2 - 10.1145/2830567

DO - 10.1145/2830567

M3 - Journal article

AN - SCOPUS:84988037173

VL - 12

SP - 45:1-45:15

JO - A C M Transactions on Algorithms

JF - A C M Transactions on Algorithms

SN - 1549-6325

IS - 4

M1 - 45

ER -