Ε-net (computational geometry): Difference between revisions

Revision as of 01:23, 26 April 2015

Revision as of 08:15, 14 September 2016

Line 27:

because the size of this set is independent of ''P'', any set ''P'' can be described using a set of fixed size.

This facilitates the development of efficient [[approximation algorithm]]s. For example, suppose we wish to estimate an upper bound on the area of a given region ''P'', that falls inside a particular rectangle ''P''. One can estimate this to within an additive factor of ''ε'' times the area of ''P'' by first finding an ''ε''-net of ''P'', counting the proportion of elements in the ε-net falling inside the region with respect to the rectangle ''P'', and then multiplying by the area of ''P''. The runtime of the algorithm depends only on ''ε'' and not ''P''. One straightforward way to compute an ε-net with high probability is to take a sufficient number of random points, where the number of random points also depends only on ''ε''. For example, in the diagram shown, any rectangle in the unit square containing at most three points in the 1/4-net has an area of at most 3/8 + 1/4 = 5/8.

ε-nets also provide approximation algorithms for the [[NP-complete]] [[hitting set problem|hitting set]] and [[set cover problem|set cover]] problems.<ref>{{citation