Untangled Monotonic Chains and Adaptive Range Search
[.pdf]
Abstract
We present the first adaptive data structure for two-dimensional
orthogonal range search. Our data structure is adaptive in the sense that it
gives improved search performance for data with more inherent sortedness.
Given n points on the plane, the linear-space data structure can answer
range queries in O(log(n)+k+m) time, where m is the number of points in
the output and k is the minimum number of monotonic chains into which the
point set can be decomposed, which is O(sqrt(n)) in the worst case. Our
result matches the worst-case performance of other optimal-time linear-space
data structures, or surpasses them when k=o(sqrt(n)). Our data structure
can also be made implicit, requiring no extra space beyond that of the data
points themselves, in which case the query time becomes O(k log n + m).
We present a novel algorithm of independent interest to decompose a point
set into a minimum number of untangled, same-direction monotonic chains in
O(kn+n log{n}) time.
Bibtex Entry
