Home Bookmarks Papers Blog

Relative eps-Approximations in Geometry

Sariel Har-Peled and Micha Sharir.

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.

Postscript, PDF.
Slides and slides source.
SoCG submission.
Last modified: Sat Jun 9 02:16:22 CDT 2007