Range Minima Queries with Respect to a Random Permutation, and Approximate Range Counting

作者：Kaplan Haim^*; Ramos Edgar; Sharir Micha

来源：Discrete & Computational Geometry, 2011, 45(1): 3-33.

DOI：10.1007/s00454-010-9308-6

• Range searching
• Random sampling
• Approximate range counting
• Randomized incremental constructions
• Range minima queries

In approximate halfspace range counting, one is given a set P of n points in a"e (d) , and an epsilon > 0, and the goal is to preprocess P into a data structure which can answer efficiently queries of the form: Given a halfspace h, compute an estimate N such that (1-epsilon)vertical bar Pa (c) h vertical bar a parts per thousand currency signNa parts per thousand currency sign(1+epsilon)vertical bar Pa (c) h vertical bar.
Several recent papers have addressed this problem, including a study by Kaplan and Sharir (Proc. 17th Annu. ACM-SIAM Sympos. Discrete Algo., pp. 484-493, 2006), which is based, as is the present paper, on Cohen's technique for approximate range counting (Cohen in J. Comput. Syst. Sci. 55:441-453, 1997). In this approach, one chooses a small number of random permutations of P, and then constructs, for each permutation pi, a data structure that answers efficiently minimum range queries: Given a query halfspace h, find the minimum-rank element (according to pi) in Pa (c) h. By repeating this process for all chosen permutations, the approximate count can be obtained, with high probability, using a certain averaging process over the minimum-rank outputs.
In the previous study, the authors have constructed such a data structure in a"e(3), using a combinatorial result about the overlay of minimization diagrams in a randomized incremental construction of lower envelopes.
In the present work, we propose an alternative approach to the range-minimum problem, based on cuttings, which achieves better performance. Specifically, it uses, for each permutation, O(n (aOESd/2aOE <)(log log n) (c) /log (aOESd/2aOE <) n) expected storage and preprocessing time, for some constant c, and answers a range-minimum query in O(log n) expected time. We also present a different approach, based on "antennas," which is simple to implement, although the bounds on its expected storage, preprocessing, and query costs are worse by polylogarithmic factors.

• 出版日期2011-1