<p>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$.</p>

CC BY-SA 3.0
2017-11-05T20:51:47.873Z
What is $n$ here?
Sasho Nikolov
CC BY-SA 3.0
2017-11-05T21:17:00.743Z
Modulo the mystery $n$, this appears to be the same order of magnitude as I cited above.
Aryeh
CC BY-SA 3.0
2017-11-05T15:19:29.683Z
2017-11-06T08:43:10.977Z
2017-11-06T08:43:10.977Z
AlexGj
<p>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?</p>

CC BY-SA 3.0
2013-07-17T20:50:19.140Z
I see that a bound of $O(dk^2\log k)$ is given in [Theorem 1](http://noodle.cs.huji.ac.il/site/labs/learning/Papers/NNk_with_theory.ps.pdf).  Is that the best known?
Aryeh
<cg.comp-geom><machine-learning><lg.learning><convex-geometry><high-dimensional-geometry>
VC dimension of Voronoi cells in R^d?
Aryeh
# VC dimension of Voronoi cells in R^d?

(Asked by: username_0 on 2013-07-17)

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?

**Tags:** cg.comp-geom, machine-learning, lg.learning, convex-geometry, high-dimensional-geometry

> **Comments:**
> **username_0**: I see that a bound of $O(dk^2\log k)$ is given in [Theorem 1](http://noodle.cs.huji.ac.il/site/labs/learning/Papers/NNk_with_theory.ps.pdf).  Is that the best known?  

---

## 1 answers

### Answer by username_1 on 2017-11-05. Score: 1 | Accepted answer

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$.

> **Comments:**
> **username_2**: What is $n$ here?  
> **username_0**: Modulo the mystery $n$, this appears to be the same order of magnitude as I cited above.  

---

