Ε-net (computational geometry): Difference between revisions

Revision as of 09:07, 4 June 2011

Revision as of 12:38, 26 January 2012

Line 10:

Let X be a set and R be a set of subsets of X; such a pair is called a ''range space'' or [[hypergraph]], and the elements of R are called ''ranges'' or ''hyperedges''. An '''ε-net''' of a subset ''P'' of ''X'' is a subset ''N'' of ''P'' such that any range ''r''&nbsp;∈&nbsp;R with |''r''&nbsp;∩&nbsp;''P''|&nbsp;≥&nbsp;''ε''|''P''| intersects&nbsp;''N''.<ref>D. Haussler and E. Welzl. ε-nets and simplex range queries. Discrete and Computational Geometry, 2:127–151, 1987.</ref> In other words, any range that intersects at least a proportion ε of the elements of ''P'' must also intersect the ''ε''-net&nbsp;''N''.

For example, suppose ''X'' is the set of points in the two-dimensional plane, ''R'' is the set of closed filled rectangles (products of closed intervals), and ''P'' is the unit square [0,&nbsp;1]&nbsp;&times;&nbsp;[0,&nbsp;1]. Then the set RN consisting of the 8 points shown in the diagram to the right is a 1/4-net of P, because any closed filled rectangle intersecting at least 1/4 of the unit square must intersect one of these points. In fact, any (axis-parallel) square, regardless of size, will have a similar 8-point 1/4-net.

For any range space with finite [[VC dimension]] ''d'', regardless of the choice of P and ε, there exists an ε-net of ''P'' of size