Approximate halfspace range counting

Boris Aronov, Micha Sharir

    Research output: Contribution to journalArticle

    Abstract

    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
    Volume39
    Issue number7
    DOIs
    StatePublished - 2010

    Keywords

    • 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

    • Computer Science(all)
    • Mathematics(all)

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

    Cite this