On the Vapnik-Chervonenkis dimension of products of intervals in ℝ^d
We study combinatorial complexity of certain classes of products of intervals in ℝ^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 ℓ_∞^d – which denotes ^d equipped with the sup norm – equals ⌊ (3d+1)/2⌋.
READ FULL TEXT