What is the VC Dimension of the class of $k$-dimensional cross-polytope (1-norm ($l_1$) balls)?
A $k$-dimensional $l_1$ ball with radius $r\in \mathcal R$ and center $\mathbb v\in \mathcal R^k$ is
$\{\mathbb x\in\mathcal R^k: ||\mathbb x-\mathbb v||_1\le r\}$.
Namely, denote $\mathbb x = [x_1,x_2,...,x_k]$ and $\mathbb v = [v_1,v_2,...,v_k]$, A $k$-dimensional $l_1$ ball with radius $r$ and center $\mathbb v$ is
$\{\mathbb x\in\mathcal R^k, |x_1-v_1|+|x_2-v_2|+...+|x_k-v_k|\le r\}$.
