Relative $(p,ε)$-Approximations in Geometry

Details Relative $(p,ε)$-Approximations in Geometry Relative $(p,ε)$-Approximations in Geometry

2009-09-03

arxiv.org/abs/0909.0717v2

Computer Science

Computational Geometry

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Relative $(p,ε)$-Approximations in Geometry does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Relative $(p,ε)$-Approximations in Geometry, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Relative $(p,ε)$-Approximations in Geometry will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-664403