# VC dimension of Voronoi cells in R^d?

Suppose I have $k$ points in $\mathbb{R}^d$. These induce a Voronoi diagram. If I assign to each of the $k$ points a $\pm$ label, these induce a binary function on $\mathbb{R}^d$. Question: what is the VC-dimension of all such possible binary functions induced by some $k$ points and some labeling of these points?

• I see that a bound of $O(dk^2\log k)$ is given in Theorem 1. Is that the best known? – Aryeh Jul 17 '13 at 20:50

Please check Theorem 21.5, Section 21 in the book "A probabilistic Theory of Pattern Recognition (1996)" from Devroye, Gyorfi, and Lugosi. I think the following upper bound is valid: VC $\leq$ $k + (d+1)k^2\log k$.
• What is $n$ here? – Sasho Nikolov Nov 5 '17 at 20:51
• Modulo the mystery $n$, this appears to be the same order of magnitude as I cited above. – Aryeh Nov 5 '17 at 21:17