1
$\begingroup$

I have researched this topic in the last time, but no usefull results for me. So I'm here and I please you to help me with the following problem:

What is $VCdim$($\mathcal{H}$), where $\mathcal{H}$ is the class of concentric circles centred in origin in the 2D plane?

$\endgroup$
4
  • 1
    $\begingroup$ Can you please define formally this class $\mathcal{H}$? Or at least explain what "concentric circles" means, for us who aren't familiar with this concept? $\endgroup$
    – nir shahar
    Sep 10 at 11:56
  • 3
    $\begingroup$ I don't even see how concentric circles can shatter any two distinct points at the same distance from the origin, e.g., $(0,1)$ and $(1,0)$. Then the VC dimension is either $0$ or $1$ depending on the details of the model (does the circle include the boundary, and can I place a point on $(0,0)$?) $\endgroup$
    – Steven
    Sep 10 at 12:22
  • $\begingroup$ @Steven Well, since the circles are pairwise disjoint, they cannot shatter any set of two distinct points. So that should be the answer. $\endgroup$ Sep 10 at 12:30
  • 1
    $\begingroup$ @nirshahar en.wikipedia.org/wiki/Concentric_objects $\endgroup$ Sep 10 at 12:30
1
$\begingroup$

You haven't explained what you mean by circle. Let me consider three possible interpretations:

  1. The set of points at distance exactly $r$ from the origin, for some $r$.
  2. The set of points at distance at most $r$ from the origin, for some $r$.
  3. The set of points at distance less than $r$ from the origin, for some $r$.

In all cases, it is easy to see that the concept class shatters any single point except, possibly, the origin. In contrast, we can show that no set of two points is shattered, and so the VC dimension is 1. Indeed, if $x,y$ are at the same distance from the origin and $C$ is an origin-centered circle, then $x \in C$ iff $y \in C$, and so $\{x,y\}$ is not shattered. If $x$ is closer to the origin from $y$, then in case 1, no origin-centered circle contains both, and in the other two cases, no origin-centered circle contains $y$ but not $x$; in all cases, $\{x,y\}$ is not shattered.

$\endgroup$
1
  • 1
    $\begingroup$ Only 1. is a circle; 2. and 3. are disks. $\endgroup$ Sep 11 at 11:49

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.