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 that is better than the worst case [8]; in this case,
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 be made implicit,
requiring no extra space beyond that of the data points themselves [16], in which
case the query time becomes O(k log n+m). We also present a novel algorithm
of independent interest to decompose a point set into a minimum number of
untangled, similarly directed monotonic chains in O(k
2n + n log n) time.
Bibtex Entry
