How to net a lot with little: Small ε-nets for disks and halfspaces
J Matoušek, R Seidel, E Welzl - … of the sixth annual symposium on …, 1990 - dl.acm.org
J Matoušek, R Seidel, E Welzl
Proceedings of the sixth annual symposium on Computational geometry, 1990•dl.acm.orgIt 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.
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.
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.
ACM Digital Library