Ε-net (computational geometry): Difference between revisions

Revision as of 19:51, 24 March 2013

Revision as of 01:23, 26 April 2015

Line 21:

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, 1] × [0, 1]. Then the set N 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

: <math>O\left(\frac{d}{\varepsilon} \log \frac{d}{\varepsilon}\right);</math>