<p>As Sasho and Huck mentioned in their comments, "shattering means that you have to be able to separate all +/- labelings of the same set of points, given the function class." </p>

<p>Therefore, since the set of points on a line is never separable by the class of triangles, it is not a valid set of points to decide the VC-dimension this class. </p>

CC BY-SA 3.0
2015-03-17T04:51:57.563Z
2015-03-18T20:18:04.013Z
2015-03-18T20:18:04.013Z
Daniel
<p>I have been reading in multiple places (e.g. [1], section 4) that the VC-dimension of the class of triangles (in 2D space) is 7. 
The issue is that, for the case when 4 points lying on a straight line with alternating signs (like - + - +), I don't see why a triangle could separate the points. Where am I making mistake? </p>

<p>[1] <a href="http://www.igi.tugraz.at/lehre/CI/SS08/tutorials/VC_examples/VC_examples.pdf" rel="nofollow">http://www.igi.tugraz.at/lehre/CI/SS08/tutorials/VC_examples/VC_examples.pdf</a> </p>

CC BY-SA 3.0
2015-03-17T00:47:14.553Z
You are getting the quantifiers in the definition of VC dimension wrong. The VC dimension being 7 means that *there exists* a set of 7 points that can be shattered and *no set* of 8 points can be shattered
Sasho Nikolov
CC BY-SA 3.0
2015-03-17T01:09:24.827Z
I am confused now. The thing is I can always find a set of 8 points such that a triangle shatters it. Draw a triangle, put 4 points inside it, and four points outside it. Right?
Daniel
CC BY-SA 3.0
2015-03-17T02:06:40.320Z
@Daniel: Shattering means that you have to be able to separate *all* +/- labellings of the same set of points, I think.
Huck Bennett
CC BY-SA 3.0
2015-03-17T04:39:47.603Z
@HuckBennett oh this makes sense now!
Daniel
CC BY-SA 3.0
2015-03-18T09:38:47.793Z
A personal pet peeve, from teaching this stuff for years... A triangle (or any single concept) does NOT shatter a set of points. Only a CLASS of concepts can shatter a set.
Aryeh
CC BY-SA 3.0
2015-03-18T20:19:28.497Z
Do you think the answer I have written below is correct then?
Daniel
CC BY-SA 3.0
2015-04-18T02:09:45.487Z
I don't think this is a research level question, and therefore it probably doesn't belong on this site.
Lev Reyzin
<cg.comp-geom><machine-learning><lg.learning><computational-geometry>
VC-dimension of triangles in 2D space
Daniel
# VC-dimension of triangles in 2D space

(Asked by: username_0 on 2015-03-17)

I have been reading in multiple places (e.g. [1], section 4) that the VC-dimension of the class of triangles (in 2D space) is 7.
The issue is that, for the case when 4 points lying on a straight line with alternating signs (like - + - +), I don't see why a triangle could separate the points. Where am I making mistake?

[1] <http://www.igi.tugraz.at/lehre/CI/SS08/tutorials/VC_examples/VC_examples.pdf>

**Tags:** cg.comp-geom, machine-learning, lg.learning, computational-geometry
> **Comments:**
> **username_1**: You are getting the quantifiers in the definition of VC dimension wrong. The VC dimension being 7 means that *there exists* a set of 7 points that can be shattered and *no set* of 8 points can be shattered  
> **username_0**: I am confused now. The thing is I can always find a set of 8 points such that a triangle shatters it. Draw a triangle, put 4 points inside it, and four points outside it. Right?  
> **username_2**: @Daniel: Shattering means that you have to be able to separate *all* +/- labellings of the same set of points, I think.  
> **username_0**: @HuckBennett oh this makes sense now!  
> **username_3**: A personal pet peeve, from teaching this stuff for years... A triangle (or any single concept) does NOT shatter a set of points. Only a CLASS of concepts can shatter a set.  
> **username_0**: Do you think the answer I have written below is correct then?  
> **username_4**: I don't think this is a research level question, and therefore it probably doesn't belong on this site.  

---

## 1 answers

### Answer by username_0 on 2015-03-17. Score: 0 | Accepted answer

As Sasho and Huck mentioned in their comments, "shattering means that you have to be able to separate all +/- labelings of the same set of points, given the function class."

Therefore, since the set of points on a line is never separable by the class of triangles, it is not a valid set of points to decide the VC-dimension this class.


---

