We re-examine the notion of relative $(p,\eps)$-approximations, recently
introduced in [CKMS06], and establish upper bounds on their size, in general
range spaces of finite VC-dimension, using the sampling theory developed in
[LLS01] and in several earlier studies [Pol86, Hau92, Tal94]. 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,\eps)$-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,\eps)$-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.