Return to Revisions

Consider $n\in\mathbb N$, $x_1,...,x_n\in\mathbb R^d$. We cut $\mathbb R^d$ along the $N=\frac{n(n-1)}2$ hyperplanes $d(x_i,x)=d(x,x_j)$ for $1\leq i<j\leq n$. This makes at most $P_d(N)=\dbinom{N+1}{0}+\dbinom{N+1}{1}+...+\dbinom{N+1}{d}$ open regions. Note that $P_n$ is of degree $d$. To each open region corresponds a permutation $\sigma$ (the indexes 1 to $n$ sorted from the closest $x_i$ to the furthest). When picking a center and radius, the set of indices in the ball corresponds to the first values of the corresponding $\sigma$. Thus, from each set center, we can at most obtain $n+1$ different sets. If we allow the center to move, we obtain $(n+1)P_d(n)$ possible sets. Thus, with $k$ different centers, we have at most $\big((n+1)P_d(N)\big)^k$ sets. If $n$ is the VC dimension, we have \begin{align*} 2^n&\leq\big((n+1)P_d(N)\big)^k\\ n\ln(2)&\leq k\ln\big((n+1)P_d(\frac{n(n-1)}2)\big)\\ n&\underset{k\to\infty}=O\Big( k(2d+1)\ln(n)\Big)\\ n&\underset{k\to\infty}=O\Big( k\big((2d+1)\ln(n)+\ln\big(\frac{(n+1)P_d(\frac{n(n-1)}2)}{n^{2d+1}}\big)\big)\Big)\\ \end{align*} This concludes the proof for fixed $d$. When $d$ moves, all that is left is to control $\ln\big(n^{-2d}P_d(\frac{n(n-1)}2)\big)$.