| Range minima queries with respect to a random permutation, and approximate range counting, Discrete Comput (2009) | |||||||||||||||
Abstract | |||||||||||||||
| In approximate halfspace range counting, one is given a set P of n points in R d, and an ε> 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−ε)|P ∩h | ≤ N ≤ (1+ε)|P ∩h|. Several recent papers have addressed this problem, including a study by the authors [18], which is based, as is the present paper, on Cohen’s technique for approximate range counting [9]. In this approach, one chooses a small number of random permutations of P, and then constructs, for each permutation π, a data structure that answers efficiently minimum range queries: Given a query halfspace h, find the minimum-rank element (according to π) in P ∩ 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 R 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, | |||||||||||||||
Details der Publikation | |||||||||||||||
| |||||||||||||||