On the Vapnik-Chervonenkis dimension of products of intervals in ${\mathbb{R}}^d$

Abstract

We study combinatorial complexity of certain classes of products of intervals in ${\mathbb{R}}^d$, from the point of view of Vapnik-Chervonenkis geometry. As a consequence of the obtained results, we conclude that the Vapnik-Chervonenkis dimension of the set of balls in ${\ell }_{\infty }^d$ -- which denotes ${\mathbb{R}}^d$ equipped with the sup norm -- equals $\lfloor (3d+1)/2\rfloor$.