On approximate halfspace range counting and relative epsilon-approximations

Boris Aronov, Sariel Har-Peled, Micha Sharir

    Research output: Chapter in Book/Report/Conference proceedingConference contribution


    The paper consists of two major parts. In the first part, we re-examine relative ε-approximations, previously studied in [12, 13, 18, 25], and their relation to certain geometric problems, most notably to approximate range counting. Wegive a simple constructive proof of their existence in general range spaces with finite VC dimension, and of a sharp bound on their size, close to the best known one. We then give a construction of smaller-size relative ε-approximations for range spaces that involve points and halfspaces in two and higher dimensions. The planar construction is based on a new structure-spanning trees with small relative crossing number, which we believe to be of independent interest. In the second part, we consider the approximate halfspace range-counting problem in Rd with relative error ε, and show that relative ε-approximations, combined with the shallow partitioning data structures of Matouŝek, yields ef- ficient solutions to this problem. For example, one of our data structures requires linear storage and O(n1+δ) preprocessingtime, for any > 0, and answers a query in time O(ε-n1-1/bd/2c2b log n), for any > 2/bd/2c; the choice of and affects b and the implied constants. Several variants and extensions are also discussed.

    Original languageEnglish (US)
    Title of host publicationProceedings of the Twenty-third Annual Symposium on Computational Geometry, SCG'07
    Number of pages10
    StatePublished - 2007
    Event23rd Annual Symposium on Computational Geometry, SCG'07 - Gyeongju, Korea, Republic of
    Duration: Jun 6 2007Jun 8 2007

    Publication series

    NameProceedings of the Annual Symposium on Computational Geometry


    Other23rd Annual Symposium on Computational Geometry, SCG'07
    Country/TerritoryKorea, Republic of


    • Approximate range queries
    • Discrepancy
    • Epsilon-approximations
    • Halfspaces
    • Partition trees
    • Queries
    • Range
    • Range spaces
    • VC-dimension

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Geometry and Topology
    • Computational Mathematics


    Dive into the research topics of 'On approximate halfspace range counting and relative epsilon-approximations'. Together they form a unique fingerprint.

    Cite this