TY - JOUR

T1 - Untangled monotonic chains and adaptive range search

AU - Arroyuelo, Diego

AU - Claude, Francisco

AU - Dorrigiv, Reza

AU - Durocher, Stephane

AU - He, Meng

AU - López-Ortiz, Alejandro

AU - Munro, J. Ian

AU - Nicholson, Patrick K.

AU - Salinger, Alejandro

AU - Skala, Matthew

PY - 2011

Y1 - 2011

N2 - 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~teDemaine:Adaptive; 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(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(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(n)$. Our data structure can be made implicit, requiring no extra space beyond that of the data points themselves~teMunro:Implicit, 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.

AB - 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~teDemaine:Adaptive; 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(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(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(n)$. Our data structure can be made implicit, requiring no extra space beyond that of the data points themselves~teMunro:Implicit, 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.

M3 - Journal article

SN - 0304-3975

VL - 412

SP - 4200

EP - 4211

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 32

ER -