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