ABSTRACT
The use of random samples to approximate properties of geometric configurations has been an influential idea for both combinatorial and algorithmic purposes. This chapter considers two related notions— ϵ $ \epsilon $ https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9781315119601/fb8178cb-c53c-4311-b072-eff5ec016aba/content/inline-math47_7.tif"/> -approximations and ϵ $ \epsilon $ https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9781315119601/fb8178cb-c53c-4311-b072-eff5ec016aba/content/inline-math47_8.tif"/> -nets—that capture the most important quantitative properties that one would expect from a random sample with respect to an underlying geometric configuration. An example problem: given a set P of points in the plane and a parameter ϵ > 0 $ \epsilon>0 $ https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9781315119601/fb8178cb-c53c-4311-b072-eff5ec016aba/content/inline-math47_9.tif"/> , is it possible to choose a set N of O ( 1 ϵ ) $ O(\frac{1}{\epsilon }) $ https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9781315119601/fb8178cb-c53c-4311-b072-eff5ec016aba/content/inline-math47_10.tif"/> points of P such that N contains at least one point from each disk containing ϵ | P | $ \epsilon |P| $ https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9781315119601/fb8178cb-c53c-4311-b072-eff5ec016aba/content/inline-math47_11.tif"/> points of P? More generally, what is the smallest non-empty set A ⊆ P $ A \subseteq P $ https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9781315119601/fb8178cb-c53c-4311-b072-eff5ec016aba/content/inline-math47_12.tif"/> that can be chosen such that for any disk D in the plane, the proportion of points of P contained in D is within ϵ $ \epsilon $ https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9781315119601/fb8178cb-c53c-4311-b072-eff5ec016aba/content/inline-math47_13.tif"/> to the proportion of points of A contained in D? In both these cases, a random sample provides an answer “in expectation,” establishing worst-case guarantees is the topic of this chapter.
