We re-examine relative eps-approximations, previously studied in
[Pol86, Hau92, LLS01, CKMS06], and their relation to certain geometric
problems. We give 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 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. We also consider applications of the new
structures for approximate range counting and related problems.