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?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ I see that a bound of $O(dk^2\log k)$ is given in Theorem 1. Is that the best known? $\endgroup$– AryehJul 17, 2013 at 20:50
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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$.
-
-
2$\begingroup$ Modulo the mystery $n$, this appears to be the same order of magnitude as I cited above. $\endgroup$– AryehNov 5, 2017 at 21:17