The VC-dimension of k-vertex d-polytopes
arXiv:2004.04841v27 citations
AI Analysis
This provides a theoretical bound for researchers in computational geometry and learning theory, addressing an incremental advance in understanding polytope complexity.
The paper tackled the problem of bounding the VC-dimension of k-vertex polytopes in d-dimensional space, showing it is at most 8d^2k log_2 k, which answers a long-standing question in computational geometry.
In this short note, we show that the VC-dimension of the class of $k$-vertex polytopes in $\mathbb R^d$ is at most $8d^2k\log_2k$, answering an old question of Long and Warmuth.