Abstract
In approximate halfspace range counting, one is given a set P of n points in ℝ
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|.
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 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 π, 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.
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 π, 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 ℝ3, using a combinatorial result about the overlay of minimization diagrams in a randomized incremental construction of lower
envelopes.
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
⌊d/2⌋(log log n)
c
/log ⌊d/2⌋
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.
performance. Specifically, it uses, for each permutation, O(n
⌊d/2⌋(log log n)
c
/log ⌊d/2⌋
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.
- Content Type Journal Article
- DOI 10.1007/s00454-010-9308-6
- Authors
- Haim Kaplan, School of Computer Science, Tel Aviv University, Tel Aviv, 69978 Israel
- Edgar Ramos, Department of Computer Science, Universidad Nacional de Colombia, Medellín, Colombia
- Micha Sharir, School of Computer Science, Tel Aviv University, Tel Aviv, 69978 Israel
- Journal Discrete and Computational Geometry
- Online ISSN 1432-0444
- Print ISSN 0179-5376
No hay comentarios:
Publicar un comentario
Nota: solo los miembros de este blog pueden publicar comentarios.