The VC-dimension of K-vertex D-polytopes (Q2663418)

A range space \((X,\mathcal{F})\) is a pair of a set \(X\) and a collection of subsets \(\mathcal{F}\) of \(X\). A set \(Y\subset X\) is shattered by \(\mathcal{F}\) if for any \(Z\subset Y\) there is \(F'\in \mathcal{F}\) such that \(F'\cap Z = F'\). The \(VC\)-dimension of a collection of sets is the size of the largest shattered subset \(Y\) of \(X\). \par The author proves that the VC-dimension of the class of \(k\)-vertex polytopes in \(\mathbb{R}^d\) is \par (1) at most \(8d^2 k \log_2 k\), and \par (2) at least \(\frac{1}{3} kd\). \par Statement (1) answers an old question of \textit{P. M. Long} and \textit{M. K. Warmuth} [Inf. Comput. 113, No. 2, 230--252 (1994; Zbl 0821.68102)].