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).