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 (Demaine et al., 2000) [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(logn+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 (Munro and Suwanda, 1980) [16], in which case the query time becomes O(klogn+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+nlogn) time. |
Year | DOI | Venue |
---|---|---|
2011 | 10.1016/j.tcs.2011.01.037 | Theoretical Computer Science |
Keywords | DocType | Volume |
Monotonic chain,Data structure,monotonic chain,data point,query time,Computational geometry,minimum number,Adaptive,optimal-time linear space data,Range search,data structure,Implicit,Untangled monotonic chain,Untangling,adaptive range search,linear space data structure,Range query,worst case,extra space,adaptive data structure | Journal | 412 |
Issue | ISSN | Citations |
32 | Theoretical Computer Science | 6 |
PageRank | References | Authors |
0.49 | 13 | 10 |
Name | Order | Citations | PageRank |
---|---|---|---|
Diego Arroyuelo | 1 | 208 | 12.97 |
Francisco Claude | 2 | 554 | 26.10 |
Reza Dorrigiv | 3 | 176 | 14.02 |
Stephane Durocher | 4 | 342 | 42.89 |
Meng He | 5 | 308 | 22.04 |
Alejandro López-Ortiz | 6 | 1252 | 107.44 |
J. Ian Munro | 7 | 3010 | 462.97 |
Patrick K. Nicholson | 8 | 88 | 14.10 |
Alejandro Salinger | 9 | 151 | 12.53 |
Matthew Skala | 10 | 101 | 12.52 |