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$ I see that a bound of $O(dk^2\log k)$ is given in Theorem 1. Is that the best known? $\endgroup$ – 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$.

| cite | improve this answer | |
  • $\begingroup$ What is $n$ here? $\endgroup$ – Sasho Nikolov Nov 5 '17 at 20:51
  • 2
    $\begingroup$ Modulo the mystery $n$, this appears to be the same order of magnitude as I cited above. $\endgroup$ – Aryeh Nov 5 '17 at 21:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.