How to net a lot with little: small ε-nets for disks and halfspaces
Jiřı́ Matoušek, Raimund Seidel, Emo Welzl · 1990
It is known that in general range spaces of VC-dimension d > 1 require ε-nets to be of size at least Ω(d/ε log 1/ε). We investigate the question whether this general lower bound is valid for the special range spaces that typically arise in computational geometry. We show that disks and pseudo-disks in the plane as well as halfspaces in R3 allow ε-nets of size only Ο(1/ε), which is best possible up to a multiplicative constant. The analogous questions for higher-dimensional spaces remain open.