TY - JOUR

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

AU - Har-Peled, Sariel

AU - Sharir, Micha

N1 - Funding Information:
Work on this paper by Sariel Har-Peled was partially supported by an NSF CAREER award CCR-01-32901. Work by Micha Sharir was supported by Grant 2006/194 from the US–Israel Binational Science Foundation, by NSF Grants CCF-05-14079 and CCF-08-30272, by Grants 155/05 and 338/09 from the Israel Science Fund, and by the Hermann Minkowski–MINERVA Center for Geometry at Tel Aviv University. The paper is available online at [].

PY - 2011/4

Y1 - 2011/4

N2 - 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.

AB - 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.

KW - Epsilon approximations

KW - Epsilon nets

KW - Geometric discrepancy

KW - Random sampling

KW - Range searching

KW - Relative approximations

KW - Spanning trees with low crossing number

UR - http://www.scopus.com/inward/record.url?scp=79851510960&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=79851510960&partnerID=8YFLogxK

U2 - 10.1007/s00454-010-9248-1

DO - 10.1007/s00454-010-9248-1

M3 - Article

AN - SCOPUS:79851510960

SN - 0179-5376

VL - 45

SP - 462

EP - 496

JO - Discrete and Computational Geometry

JF - Discrete and Computational Geometry

IS - 3

ER -