Approximate halfspace range counting

Boris Aronov, Micha Sharir

    Research output: Contribution to journalArticlepeer-review


    We present a simple scheme extending the shallow partitioning data structures of Matoušek, which supports efficient approximate halfspace range-counting queries in ℝd with relative error ε. Specifically, the problem is, given a set P of n points in ℝd, to preprocess them into a data structure that returns, for a query halfspace h, a number t so that (1 - ε)|h ∩ P| ≤ t ≤ (1 + ε)| h ∩P|. One of our data structures requires linear storage and O(n1+δ) preprocessing time, for any δ > 0, and answers a query in time O(ε n1-1/⌊d/2⌋2b log* n) for any γ > 2/⌊d/2⌋; the choice of γ and δ affects b and the implied constants. Several variants and extensions are also discussed. As presented, the construction of the structure is mostly deterministic, except for one critical randomized step, and so are the query, storage, and preprocessing costs. The quality of approximation, for every query, is guaranteed with high probability. The construction can also be fully derandomized, at the expense of increasing preprocessing time.

    Original languageEnglish (US)
    Pages (from-to)2704-2725
    Number of pages22
    JournalSIAM Journal on Computing
    Issue number7
    StatePublished - 2010


    • Approximation algorithms
    • Cuttings
    • Geometric algorithms
    • Geometric sampling
    • Hyperplane arrangements
    • Partition trees
    • Range counting
    • Range searching
    • Relative approximations
    • Shallow cuttings
    • Shallow partition trees

    ASJC Scopus subject areas

    • General Computer Science
    • General Mathematics


    Dive into the research topics of 'Approximate halfspace range counting'. Together they form a unique fingerprint.

    Cite this