Return to Answer

We prove that for $p\in\{1,2,\infty\}$ $$dim_{VC}\underset{\substack{k\to\infty\\d\to\infty}}=O\Big( dk\ln(dk)\Big).$$ for the family of functions $$A_p=\{(x,t_1,...,t_k)\mapsto1(\min_i||x-q_i||_p-t_i>0)|(x_1,...,x_k)\in(\mathbb R^d)^k\},$$ which is still bigger than the dimension of $$B=\{(x,t)\mapsto1(\min_q||x-q_i||_p-t>0)|Q\subset\mathbb R^d, \#(Q)=k\}.$$ $$=\{(x,c_Qt)\mapsto1(c_Q\min_q||x-q_i||_p-t>0)|Q\subset\mathbb R^d, \#(Q)=k\}.$$ We note $Norm(\cdot)=||\cdot||_p$

Using $k$ clusters of $(d+1)$ points laid out in simplexes, we can find that $dim_{VC}(A_p)\geq(d+1)k$, so $d=_{k,d\to\infty}o(dim_{VC}(A_p))$. This relation will be of use later.

Consider $n$ the VC-dimension of $A_p$ and a set $x_1,...,x_n\in\mathbb R^d$ that we can pulverize. We first try to give an upper bound to the cardinal of $\big\{\{x_i\}_{1\leq i\leq n}\cap f^{-1}(\{0\})\big\}_{f\in A_p}$, then use it to derive a majoration of $n$.

For every $1\leq i\not=j\leq n$, we can choose some hyperplane $H_{i,j}=H_{j,i}$ separating the sets $Norm(q-x_i)<Norm(q-x_j)$ and $Norm(q-x_i)>Norm(q-x_j)$. To each $q\in\mathbb R^d\setminus(\bigcup_{i,j}H_{i,j})$, associate $\sigma_q$ such that $\sigma_q(i)<\sigma_q(j)$ iff $q$ and $x_i$ are on the same side of $H_{i,j}$. If $q\in H_{i,j}$, set $\sigma_q$ to be the permutation of a neighbouring region of $\mathbb R^d\setminus(\bigcup_{i,j}H_{i,j})$.

If we note $N=\frac{n(n-1)}2$ the number of hyperplanes, $\mathbb R^d\setminus(\bigcup_{i,j}H_{i,j})$ has 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$. For $k$ and $d$ going to $\infty$, we have $d=_{d,k\to\infty}o(dk)=_{d,k\to\infty}o(N)$, so we should have $P_d(N)\sim_{k,d\to\infty}\binom{N+1}d\frac{((N+1)/d-0.5)^de^d}{\sqrt{2\pi k}}.$ Without proof of the former, let us use the much coarser $P_d(N)\leq (d+1)\binom{N+1}d$.

For every $q\in\mathbb R^d$, $Norm(q-x_{\sigma_q(i)})$ is non decreasing, so when we picking a radius $t$, the ball of center $q$ and radius $t$ can have at most $n+1$ intersections with $\{x_1,...,x_n\}$ : no points, $\{x_{\sigma_q(1)}\}$, $\{x_{\sigma_q(1)},x_{\sigma_q(2)}\}$,... or all the $x_i$. For a ball of center $q_i$ and radius $t_i$, choosing $q_i$ gives at most $P_d(N)$ possibilities for $\sigma_q$, wich then translates to at most $(n+1)P_d(N)$ possibilities for $B(q_i,t_i)\cap\{x_i\}_{i\leq n}$. With $k$ balls, we get $\big((n+1)P_d(N)\big)^k$ possible sets.

Since we can pulverize $x_1,...,x_n$, 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&\leq \frac{k}{\ln(2)}\ln\left((n+1)(d+1)\binom{N}{d}\right)\\ &\underset{\substack{k\to\infty\\d\to\infty}}=O\Big( k\ln(nd\frac{(\frac{N}d-\frac12)^d\mathrm e^d}{\sqrt d})\Big)\\ &\underset{\substack{k\to\infty\\d\to\infty}}=O\Big( k\big(\ln(n)+\ln(d)+d\ln(\frac{N}d-\frac12)+d-\frac12\ln(d)\big)\Big)\\ &\underset{\substack{k\to\infty\\d\to\infty}}=O\Big( dk\ln(\frac{N}d)\Big)\\ &\underset{\substack{k\to\infty\\d\to\infty}}=O\Big( dk\ln(n)\Big)\\ &\underset{\substack{k\to\infty\\d\to\infty}}=O\Big( dk\ln(dk\ln(n))\Big)\\ &\underset{\substack{k\to\infty\\d\to\infty}}=O\Big( dk\ln(dk)\Big)+O\Big(dk\ln(\ln(n))\Big)\\ &\underset{\substack{k\to\infty\\d\to\infty}}=O\Big( dk\ln(dk)\Big)+o\Big(dk\ln(n)\Big)\\ &\underset{\substack{k\to\infty\\d\to\infty}}=O\Big( dk\ln(dk)\Big) \end{align*} For $k,d\to\infty$, we used an equivalent for $\binom{N}k$ when $k=o(N)$, and used the fact that $\ln(N)=O( \ln(n))$. Using the better equivalent $P_d(N)\sim\binom{N+1}d$ (if true) should provide $O(dk\ln(k)).$

Not an answer to the question

We prove that for $p=2$ $$dim_{VC}\underset{\substack{k\to\infty\\d\to\infty}}=O\Big( dk\ln(dk)\Big).$$ for the family of functions $$A_p=\{(x,t_1,...,t_k)\mapsto1(\min_i||x-q_i||_p-t_i>0)|(x_1,...,x_k)\in(\mathbb R^d)^k\},$$ which is still bigger than the dimension of $$B=\{(x,t)\mapsto1(\min_q||x-q_i||_p-t>0)|Q\subset\mathbb R^d, \#(Q)=k\}.$$ $$=\{(x,c_Qt)\mapsto1(c_Q\min_q||x-q_i||_p-t>0)|Q\subset\mathbb R^d, \#(Q)=k\}.$$ We note $Norm(\cdot)=||\cdot||_p$

Using $k$ clusters of $(d+1)$ points laid out in simplexes, we can find that $dim_{VC}(A_p)\geq(d+1)k$, so $d=_{k,d\to\infty}o(dim_{VC}(A_p))$. This relation will be of use later.

Consider $n$ the VC-dimension of $A_p$ and a set $x_1,...,x_n\in\mathbb R^d$ that we can pulverize. We first try to give an upper bound to the cardinal of $\big\{\{x_i\}_{1\leq i\leq n}\cap f^{-1}(\{0\})\big\}_{f\in A_p}$, then use it to derive a majoration of $n$.

For every $1\leq i\not=j\leq n$, we can choose some hyperplane $H_{i,j}=H_{j,i}$ separating the sets $Norm(q-x_i)<Norm(q-x_j)$ and $Norm(q-x_i)>Norm(q-x_j)$. To each $q\in\mathbb R^d\setminus(\bigcup_{i,j}H_{i,j})$, associate $\sigma_q$ such that $\sigma_q(i)<\sigma_q(j)$ iff $q$ and $x_i$ are on the same side of $H_{i,j}$. If $q\in H_{i,j}$, set $\sigma_q$ to be the permutation of a neighbouring region of $\mathbb R^d\setminus(\bigcup_{i,j}H_{i,j})$.

If we note $N=\frac{n(n-1)}2$ the number of hyperplanes, $\mathbb R^d\setminus(\bigcup_{i,j}H_{i,j})$ has 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$. For $k$ and $d$ going to $\infty$, we have $d=_{d,k\to\infty}o(dk)=_{d,k\to\infty}o(N)$, so we should have $P_d(N)\sim_{k,d\to\infty}\binom{N+1}d\frac{((N+1)/d-0.5)^de^d}{\sqrt{2\pi k}}.$ Without proof of the former, let us use the much coarser $P_d(N)\leq (d+1)\binom{N+1}d$.

For every $q\in\mathbb R^d$, $Norm(q-x_{\sigma_q(i)})$ is non decreasing, so when we picking a radius $t$, the ball of center $q$ and radius $t$ can have at most $n+1$ intersections with $\{x_1,...,x_n\}$ : no points, $\{x_{\sigma_q(1)}\}$, $\{x_{\sigma_q(1)},x_{\sigma_q(2)}\}$,... or all the $x_i$. For a ball of center $q_i$ and radius $t_i$, choosing $q_i$ gives at most $P_d(N)$ possibilities for $\sigma_q$, wich then translates to at most $(n+1)P_d(N)$ possibilities for $B(q_i,t_i)\cap\{x_i\}_{i\leq n}$. With $k$ balls, we get $\big((n+1)P_d(N)\big)^k$ possible sets.

Since we can pulverize $x_1,...,x_n$, 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&\leq \frac{k}{\ln(2)}\ln\left((n+1)(d+1)\binom{N}{d}\right)\\ &\underset{\substack{k\to\infty\\d\to\infty}}=O\Big( k\ln(nd\frac{(\frac{N}d-\frac12)^d\mathrm e^d}{\sqrt d})\Big)\\ &\underset{\substack{k\to\infty\\d\to\infty}}=O\Big( k\big(\ln(n)+\ln(d)+d\ln(\frac{N}d-\frac12)+d-\frac12\ln(d)\big)\Big)\\ &\underset{\substack{k\to\infty\\d\to\infty}}=O\Big( dk\ln(\frac{N}d)\Big)\\ &\underset{\substack{k\to\infty\\d\to\infty}}=O\Big( dk\ln(n)\Big)\\ &\underset{\substack{k\to\infty\\d\to\infty}}=O\Big( dk\ln(dk\ln(n))\Big)\\ &\underset{\substack{k\to\infty\\d\to\infty}}=O\Big( dk\ln(dk)\Big)+O\Big(dk\ln(\ln(n))\Big)\\ &\underset{\substack{k\to\infty\\d\to\infty}}=O\Big( dk\ln(dk)\Big)+o\Big(dk\ln(n)\Big)\\ &\underset{\substack{k\to\infty\\d\to\infty}}=O\Big( dk\ln(dk)\Big) \end{align*} For $k,d\to\infty$, we used an equivalent for $\binom{N}k$ when $k=o(N)$, and used the fact that $\ln(N)=O( \ln(n))$. Using the better equivalent $P_d(N)\sim\binom{N+1}d$ (if true) should provide $O(dk\ln(k)).$

We prove that for $p\in\{1,2,\infty\}$ $$dim_{VC}\underset{\substack{k\to\infty\\d\to\infty}}=O\Big( dk\ln(dk)\Big).$$ for the family of functions $$A_p=\{(x,t_1,...,t_k)\mapsto1(\min_i||x-q_i||_p-t_i>0)|(x_1,...,x_k)\in(\mathbb R^d)^k\},$$ which is still bigger than the dimension of $$B=\{(x,t)\mapsto1(\min_q||x-q_i||_p-t>0)|Q\subset\mathbb R^d, \#(Q)=k\}.$$ $$=\{(x,c_Qt)\mapsto1(c_Q\min_q||x-q_i||_p-t>0)|Q\subset\mathbb R^d, \#(Q)=k\}.$$ We note $Norm(\cdot)=|\cdot||_p$

Using $k$ clusters of $(d+1)$ points laid out in simplexes, we can find that $dim_{VC}(A_p)\geq(d+1)k$.

Consider $n$ the VC-dimension of $A_p$ and a set $x_1,...,x_n\in\mathbb R^d$ that we can pulverize. For every $1\leq i\not=j\leq n$, we can choose some hyperplane $H_{i,j}=H_{j,i}$ separating the sets $Norm(q-x_i)<Norm(q-x_j)$ and $Norm(q-x_i)>Norm(q-x_j)$. To each $q\in\mathbb R^d\setminus(\bigcup_{i,j}H_{i,j})$, associate $\sigma_q$ such that $\sigma_q(i)<\sigma_q(j)$ iff $q$ and $x_i$ are on the same side of $H_{i,j}$. If $q\in H_{i,j}$, set $\sigma_q$ to be the permutation of a neighbouring region of $\mathbb R^d\setminus(\bigcup_{i,j}H_{i,j})$.

If we note $N=\frac{n(n-1)}2$ the number of hyperplanes, $\mathbb R^d\setminus(\bigcup_{i,j}H_{i,j})$ has 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$. For $k$ and $d$ going to $\infty$, we have $d=_{d,k\to\infty}o(dk)=_{d,k\to\infty}o(N)$, so we should have $P_d(N)\sim_{k,d\to\infty}\binom{N+1}d\frac{((N+1)/d-0.5)^de^d}{\sqrt{2\pi k}}.$ Without proof of the former, let us use the much coarser $P_d(N)\leq (d+1)\binom{N+1}d$.

For every $q\in\mathbb R^d$, $Norm(q-x_{\sigma_q(i)})$ is non decreasing, so when we picking a radius $t$, the ball of center $q$ and radius $t$ can have at most $n+1$ intersections with $\{x_1,...,x_n\}$ : no points, $\{x_{\sigma_q(1)}\}$, $\{x_{\sigma_q(1)},x_{\sigma_q(2)}\}$,... or all the $x_i$. For a ball of center $q_i$ and radius $t_i$, choosing $q_i$ gives at most $P_d(N)$ possibilities for $\sigma_q$, wich then translates to at most $(n+1)P_d(N)$ possibilities for $B(q_i,t_i)\cap\{x_i\}_{i\leq n}$. With $k$ balls, we get $\big((n+1)P_d(N)\big)^k$ possible sets.

Since we can pulverize $x_1,...,x_n$, 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&\leq \frac{k}{\ln(2)}\ln\left((n+1)(d+1)\binom{N}{d}\right)\\ &\underset{\substack{k\to\infty\\d\to\infty}}=O\Big( k\ln(nd\frac{(\frac{N}d-\frac12)^d\mathrm e^d}{\sqrt d})\Big)\\ &\underset{\substack{k\to\infty\\d\to\infty}}=O\Big( k\big(\ln(n)+\ln(d)+d\ln(\frac{N}d-\frac12)+d-\frac12\ln(d)\big)\Big)\\ &\underset{\substack{k\to\infty\\d\to\infty}}=O\Big( dk\ln(\frac{N}d)\Big)\\ &\underset{\substack{k\to\infty\\d\to\infty}}=O\Big( dk\ln(n)\Big)\\ &\underset{\substack{k\to\infty\\d\to\infty}}=O\Big( dk\ln(dk\ln(n))\Big)\\ &\underset{\substack{k\to\infty\\d\to\infty}}=O\Big( dk\ln(dk)\Big)+O\Big(dk\ln(\ln(n))\Big)\\ &\underset{\substack{k\to\infty\\d\to\infty}}=O\Big( dk\ln(dk)\Big)+o\Big(dk\ln(n)\Big)\\ &\underset{\substack{k\to\infty\\d\to\infty}}=O\Big( dk\ln(dk)\Big) \end{align*} For $k,d\to\infty$, we used an equivalent for $\binom{N}k$ when $k=o(N)$, and used the fact that $\ln(N)=O( \ln(n))$. Using the better equivalent $P_d(N)\sim\binom{N+1}d$ should provide $O(dk\ln(k)).$

We prove that for $p\in\{1,2,\infty\}$ $$dim_{VC}\underset{\substack{k\to\infty\\d\to\infty}}=O\Big( dk\ln(dk)\Big).$$ for the family of functions $$A_p=\{(x,t_1,...,t_k)\mapsto1(\min_i||x-q_i||_p-t_i>0)|(x_1,...,x_k)\in(\mathbb R^d)^k\},$$ which is still bigger than the dimension of $$B=\{(x,t)\mapsto1(\min_q||x-q_i||_p-t>0)|Q\subset\mathbb R^d, \#(Q)=k\}.$$ $$=\{(x,c_Qt)\mapsto1(c_Q\min_q||x-q_i||_p-t>0)|Q\subset\mathbb R^d, \#(Q)=k\}.$$ We note $Norm(\cdot)=||\cdot||_p$

Using $k$ clusters of $(d+1)$ points laid out in simplexes, we can find that $dim_{VC}(A_p)\geq(d+1)k$, so $d=_{k,d\to\infty}o(dim_{VC}(A_p))$. This relation will be of use later.

Consider $n$ the VC-dimension of $A_p$ and a set $x_1,...,x_n\in\mathbb R^d$ that we can pulverize. We first try to give an upper bound to the cardinal of $\big\{\{x_i\}_{1\leq i\leq n}\cap f^{-1}(\{0\})\big\}_{f\in A_p}$, then use it to derive a majoration of $n$. 

For every $1\leq i\not=j\leq n$, we can choose some hyperplane $H_{i,j}=H_{j,i}$ separating the sets $Norm(q-x_i)<Norm(q-x_j)$ and $Norm(q-x_i)>Norm(q-x_j)$. To each $q\in\mathbb R^d\setminus(\bigcup_{i,j}H_{i,j})$, associate $\sigma_q$ such that $\sigma_q(i)<\sigma_q(j)$ iff $q$ and $x_i$ are on the same side of $H_{i,j}$. If $q\in H_{i,j}$, set $\sigma_q$ to be the permutation of a neighbouring region of $\mathbb R^d\setminus(\bigcup_{i,j}H_{i,j})$.

If we note $N=\frac{n(n-1)}2$ the number of hyperplanes, $\mathbb R^d\setminus(\bigcup_{i,j}H_{i,j})$ has 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$. For $k$ and $d$ going to $\infty$, we have $d=_{d,k\to\infty}o(dk)=_{d,k\to\infty}o(N)$, so we should have $P_d(N)\sim_{k,d\to\infty}\binom{N+1}d\frac{((N+1)/d-0.5)^de^d}{\sqrt{2\pi k}}.$ Without proof of the former, let us use the much coarser $P_d(N)\leq (d+1)\binom{N+1}d$.

For every $q\in\mathbb R^d$, $Norm(q-x_{\sigma_q(i)})$ is non decreasing, so when we picking a radius $t$, the ball of center $q$ and radius $t$ can have at most $n+1$ intersections with $\{x_1,...,x_n\}$ : no points, $\{x_{\sigma_q(1)}\}$, $\{x_{\sigma_q(1)},x_{\sigma_q(2)}\}$,... or all the $x_i$. For a ball of center $q_i$ and radius $t_i$, choosing $q_i$ gives at most $P_d(N)$ possibilities for $\sigma_q$, wich then translates to at most $(n+1)P_d(N)$ possibilities for $B(q_i,t_i)\cap\{x_i\}_{i\leq n}$. With $k$ balls, we get $\big((n+1)P_d(N)\big)^k$ possible sets.

Since we can pulverize $x_1,...,x_n$, 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&\leq \frac{k}{\ln(2)}\ln\left((n+1)(d+1)\binom{N}{d}\right)\\ &\underset{\substack{k\to\infty\\d\to\infty}}=O\Big( k\ln(nd\frac{(\frac{N}d-\frac12)^d\mathrm e^d}{\sqrt d})\Big)\\ &\underset{\substack{k\to\infty\\d\to\infty}}=O\Big( k\big(\ln(n)+\ln(d)+d\ln(\frac{N}d-\frac12)+d-\frac12\ln(d)\big)\Big)\\ &\underset{\substack{k\to\infty\\d\to\infty}}=O\Big( dk\ln(\frac{N}d)\Big)\\ &\underset{\substack{k\to\infty\\d\to\infty}}=O\Big( dk\ln(n)\Big)\\ &\underset{\substack{k\to\infty\\d\to\infty}}=O\Big( dk\ln(dk\ln(n))\Big)\\ &\underset{\substack{k\to\infty\\d\to\infty}}=O\Big( dk\ln(dk)\Big)+O\Big(dk\ln(\ln(n))\Big)\\ &\underset{\substack{k\to\infty\\d\to\infty}}=O\Big( dk\ln(dk)\Big)+o\Big(dk\ln(n)\Big)\\ &\underset{\substack{k\to\infty\\d\to\infty}}=O\Big( dk\ln(dk)\Big) \end{align*} For $k,d\to\infty$, we used an equivalent for $\binom{N}k$ when $k=o(N)$, and used the fact that $\ln(N)=O( \ln(n))$. Using the better equivalent $P_d(N)\sim\binom{N+1}d$ (if true) should provide $O(dk\ln(k)).$

We prove $$dim_{VC}\underset{\substack{k\to\infty\\d\to\infty}}=O\Big( dk\ln(dk)\Big).$$

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 $n\geq (d+1)k$ (obtained with $k$ regular simplexes) so if $d$ goes to $\infty$, $k=o(n)$. \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&\leq \frac{k}{\ln(2)}\ln\left((n+1)(d+1)\binom{N}{d}\right)\\ &\underset{\substack{k\to\infty\\d\to\infty}}=O\Big( k\ln(nd\frac{(\frac{N}d-\frac12)^d\mathrm e^d}{\sqrt d})\Big)\\ &\underset{\substack{k\to\infty\\d\to\infty}}=O\Big( k\big(\ln(n)+\ln(d)+d\ln(\frac{N}d-\frac12)+d-\frac12\ln(d)\big)\Big)\\ &\underset{\substack{k\to\infty\\d\to\infty}}=O\Big( dk\ln(\frac{N}d)\Big)\\ &\underset{\substack{k\to\infty\\d\to\infty}}=O\Big( dk\ln(n)\Big)\\ &\underset{\substack{k\to\infty\\d\to\infty}}=O\Big( dk\ln(dk\ln(n))\Big)\\ &\underset{\substack{k\to\infty\\d\to\infty}}=O\Big( dk\ln(dk)\Big)+O\Big(dk\ln(\ln(n))\Big)\\ &\underset{\substack{k\to\infty\\d\to\infty}}=O\Big( dk\ln(dk)\Big)+o\Big(dk\ln(n)\Big)\\ &\underset{\substack{k\to\infty\\d\to\infty}}=O\Big( dk\ln(dk)\Big) \end{align*} For $k,d\to\infty$, we used an equivalent for $\binom{N}k$ when $k=o(N)$, and used the fact that $\ln(N)=O( \ln(n))$.

We prove that for $p\in\{1,2,\infty\}$ $$dim_{VC}\underset{\substack{k\to\infty\\d\to\infty}}=O\Big( dk\ln(dk)\Big).$$ for the family of functions $$A_p=\{(x,t_1,...,t_k)\mapsto1(\min_i||x-q_i||_p-t_i>0)|(x_1,...,x_k)\in(\mathbb R^d)^k\},$$ which is still bigger than the dimension of $$B=\{(x,t)\mapsto1(\min_q||x-q_i||_p-t>0)|Q\subset\mathbb R^d, \#(Q)=k\}.$$ $$=\{(x,c_Qt)\mapsto1(c_Q\min_q||x-q_i||_p-t>0)|Q\subset\mathbb R^d, \#(Q)=k\}.$$ We note $Norm(\cdot)=|\cdot||_p$

Using $k$ clusters of $(d+1)$ points laid out in simplexes, we can find that $dim_{VC}(A_p)\geq(d+1)k$.

Consider $n$ the VC-dimension of $A_p$ and a set $x_1,...,x_n\in\mathbb R^d$ that we can pulverize. For every $1\leq i\not=j\leq n$, we can choose some hyperplane $H_{i,j}=H_{j,i}$ separating the sets $Norm(q-x_i)<Norm(q-x_j)$ and $Norm(q-x_i)>Norm(q-x_j)$. To each $q\in\mathbb R^d\setminus(\bigcup_{i,j}H_{i,j})$, associate $\sigma_q$ such that $\sigma_q(i)<\sigma_q(j)$ iff $q$ and $x_i$ are on the same side of $H_{i,j}$. If $q\in H_{i,j}$, set $\sigma_q$ to be the permutation of a neighbouring region of $\mathbb R^d\setminus(\bigcup_{i,j}H_{i,j})$.

If we note $N=\frac{n(n-1)}2$ the number of hyperplanes, $\mathbb R^d\setminus(\bigcup_{i,j}H_{i,j})$ has 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$. For $k$ and $d$ going to $\infty$, we have $d=_{d,k\to\infty}o(dk)=_{d,k\to\infty}o(N)$, so we should have $P_d(N)\sim_{k,d\to\infty}\binom{N+1}d\frac{((N+1)/d-0.5)^de^d}{\sqrt{2\pi k}}.$ Without proof of the former, let us use the much coarser $P_d(N)\leq (d+1)\binom{N+1}d$.

For every $q\in\mathbb R^d$, $Norm(q-x_{\sigma_q(i)})$ is non decreasing, so when we picking a radius $t$, the ball of center $q$ and radius $t$ can have at most $n+1$ intersections with $\{x_1,...,x_n\}$ : no points, $\{x_{\sigma_q(1)}\}$, $\{x_{\sigma_q(1)},x_{\sigma_q(2)}\}$,... or all the $x_i$. For a ball of center $q_i$ and radius $t_i$, choosing $q_i$ gives at most $P_d(N)$ possibilities for $\sigma_q$, wich then translates to at most $(n+1)P_d(N)$ possibilities for $B(q_i,t_i)\cap\{x_i\}_{i\leq n}$. With $k$ balls, we get $\big((n+1)P_d(N)\big)^k$ possible sets.

Since we can pulverize $x_1,...,x_n$, 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&\leq \frac{k}{\ln(2)}\ln\left((n+1)(d+1)\binom{N}{d}\right)\\ &\underset{\substack{k\to\infty\\d\to\infty}}=O\Big( k\ln(nd\frac{(\frac{N}d-\frac12)^d\mathrm e^d}{\sqrt d})\Big)\\ &\underset{\substack{k\to\infty\\d\to\infty}}=O\Big( k\big(\ln(n)+\ln(d)+d\ln(\frac{N}d-\frac12)+d-\frac12\ln(d)\big)\Big)\\ &\underset{\substack{k\to\infty\\d\to\infty}}=O\Big( dk\ln(\frac{N}d)\Big)\\ &\underset{\substack{k\to\infty\\d\to\infty}}=O\Big( dk\ln(n)\Big)\\ &\underset{\substack{k\to\infty\\d\to\infty}}=O\Big( dk\ln(dk\ln(n))\Big)\\ &\underset{\substack{k\to\infty\\d\to\infty}}=O\Big( dk\ln(dk)\Big)+O\Big(dk\ln(\ln(n))\Big)\\ &\underset{\substack{k\to\infty\\d\to\infty}}=O\Big( dk\ln(dk)\Big)+o\Big(dk\ln(n)\Big)\\ &\underset{\substack{k\to\infty\\d\to\infty}}=O\Big( dk\ln(dk)\Big) \end{align*} For $k,d\to\infty$, we used an equivalent for $\binom{N}k$ when $k=o(N)$, and used the fact that $\ln(N)=O( \ln(n))$. Using the better equivalent $P_d(N)\sim\binom{N+1}d$ should provide $O(dk\ln(k)).$