You are currently browsing the tag archive for the ‘epsilon-net’ tag.

[This post is authored by Gil Kalai, who has kindly “guest blogged” this week’s “open problem of the week”. – T.]

This is a problem in discrete and convex geometry. It seeks to quantify the intuitively obvious fact that large convex bodies are so “fat” that they cannot avoid “detection” by a small number of observation points. More precisely, we fix a dimension d and make the following definition (introduced by Haussler and Welzl):

• Definition: Let $X \subset {\Bbb R}^d$ be a finite set of points, and let $0 < \epsilon < 1$. We say that a finite set $Y \subset {\Bbb R}^d$ is a weak $\epsilon$-net for X (with respect to convex bodies) if, whenever B is a convex body which is large in the sense that $|B \cap X| > \epsilon |X|$, then B contains at least one point of Y. (If Y is contained in X, we say that Y is a strong $\epsilon$-net for X with respect to convex bodies.)

For example, in one dimension, if $X = \{1,\ldots,N\}$, and $Y = \{ \epsilon N, 2 \epsilon N, \ldots, k \epsilon N \}$ where k is the integer part of $1/\epsilon$, then Y is a weak $\epsilon$-net for X with respect to convex bodies. Thus we see that even when the original set X is very large, one can create a $\epsilon$-net of size as small as $O(1/\epsilon)$. Strong $\epsilon$-nets are of importance in computational learning theory, and are fairly well understood via Vapnik-Chervonenkis (or VC) theory; however, the theory of weak $\epsilon$-nets is still not completely satisfactory.

One can ask what happens in higher dimensions, for instance when X is a discrete cube $X = \{1,\ldots,N\}^d$. It is not too hard to cook up $\epsilon$-nets of size $O_d(1/\epsilon^d)$ (by using tools such as Minkowski’s theorem), but in fact one can create $\epsilon$-nets of size as small as $O( \frac{1}{\epsilon} \log \frac{1}{\epsilon} )$ simply by taking a random subset of X of this cardinality and observing that “up to errors of $\epsilon$“, the total number of essentially different ways a convex body can meet X grows at most polynomially in $1/\epsilon$. (This is a very typical application of the probabilistic method.) On the other hand, since X can contain roughly $1/\epsilon$ disjoint convex bodies, each of which contains at least $\epsilon$ of the points in X, we see that no $\epsilon$-net can have size much smaller than $1/\epsilon$.

Now consider the situation in which X is now an arbitrary finite set, rather than a discrete cube. More precisely, let $f(\epsilon,d)$ be the least number such that every finite set X possesses at least one weak $\epsilon$-net for X with respect to convex bodies of cardinality at most $f(\epsilon,d)$. (One can also replace the finite set X with an arbitrary probability measure; the two formulations are equivalent.) Informally, f is the least number of “guards” one needs to place to prevent a convex body from covering more than $\epsilon$ of any given territory.

• Problem 1: For fixed d, what is the correct rate of growth of f as $\epsilon \to 0$?