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

    Abstract

    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
    Pages327-336
    Number of pages10
    DOIs
    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

    Other

    Other23rd Annual Symposium on Computational Geometry, SCG'07
    CountryKorea, Republic of
    CityGyeongju
    Period6/6/076/8/07

    Keywords

    • 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

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

  • Cite this

    Aronov, B., Har-Peled, S., & Sharir, M. (2007). On approximate halfspace range counting and relative epsilon-approximations. In Proceedings of the Twenty-third Annual Symposium on Computational Geometry, SCG'07 (pp. 327-336). (Proceedings of the Annual Symposium on Computational Geometry). https://doi.org/10.1145/1247069.1247128