VC-dimension
Tue, Apr 12, 2016 02:00 CEST

Definitions of VC-dimesion and \(\varepsilon\)-nets.

We bound the position of the \(0\)-cells of an arrangement of hyperplanes in \(\mathbb{R}^d\). This allows, for example, to build an hypercube that intersects all cells of the arrangement. Such an hypercube must contain at least one point of each cell of the arrangement. When \(q > 0\), in order to fix which point of a \(q\)-cell we want to include in the hypercube, it suffices to add the \(n\) hyperplanes of equation \(x_i = 0\) to the arrangement. With those additional hyperplanes, the arrangement is such that each \(q\)-cell of the arrangement with \(q > 0\) contains a \(0\)-cell of the arrangement, hence, we only need the hypercube to intersect, for each \(0\)-cell \(\nu\) of the arrangement, an hypersphere of center \(\nu\) and arbitrarily small radius. The inequalities of the polyhedral set defining our hypercube will thus only depend on the position of the \(0\)-cells of our arrangement.

A *polyhedral set* in \(\mathbb{R}^d\) is the intersection of a finite
number of closed halfspaces, and a *(convex) polytope* is a bounded polyhedral
set. This definition of a polytope is called a *halfspace representation*
(*H-representation* or *H-description*).