Relative (p, ε)-Approximations in Geometry

Sariel Har-Peled, Micha Sharir

Research output: Contribution to journalArticlepeer-review


We re-examine the notion of relative (p,ε)-approximations, recently introduced in Cohen et al. (Manuscript, 2006), and establish upper bounds on their size, in general range spaces of finite VC-dimension, using the sampling theory developed in Li et al. (J. Comput. Syst. Sci. 62:516-527, 2001) and in several earlier studies (Pollard in Manuscript, 1986; Haussler in Inf. Comput. 100:78-150, 1992; Talagrand in Ann. Probab. 22:28-76, 1994). We also survey the different notions of sampling, used in computational geometry, learning, and other areas, and show how they relate to each other. We then give constructions of smaller-size relative (p,ε)-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. Relative (p, ε)-approximations arise in several geometric problems, such as approximate range counting, and we apply our new structures to obtain efficient solutions for approximate range counting in three dimensions. We also present a simple solution for the planar case.

Original languageEnglish (US)
Pages (from-to)462-496
Number of pages35
JournalDiscrete and Computational Geometry
Issue number3
StatePublished - Apr 2011


  • Epsilon approximations
  • Epsilon nets
  • Geometric discrepancy
  • Random sampling
  • Range searching
  • Relative approximations
  • Spanning trees with low crossing number

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics


Dive into the research topics of 'Relative (p, ε)-Approximations in Geometry'. Together they form a unique fingerprint.

Cite this