Adaptive and approximate orthogonal range counting

Timothy M. Chan, Bryan T. Wilkinson

Publikation: Bidrag til tidsskrift/Konferencebidrag i tidsskrift /Bidrag til avisTidsskriftartikelForskningpeer review

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ø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.

OriginalsprogEngelsk
Artikelnummer45
TidsskriftACM Transactions on Algorithms
Vol/bind12
Nummer4
Sider (fra-til)45:1-45:15
ISSN1549-6325
DOI
StatusUdgivet - 2016

Fingeraftryk

Dyk ned i forskningsemnerne om 'Adaptive and approximate orthogonal range counting'. Sammen danner de et unikt fingeraftryk.

Citationsformater