English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

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|. 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. 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. 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.

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