Это видео недоступно.
Сожалеем об этом.
Every Polygon can be Triangulated Into Exactly n-2 Triangles | Proof by Induction
HTML-код
- Опубликовано: 12 май 2020
- Learn more about propositional logic and dive into the world of beautiful geometry at:
brilliant.org/ThinkTwice
-----------------------------------------------------------------------------------------------------------
Help me create more content by supporting Think Twice on:
► Patreon: / think_twice
► Twitter: / thinktwice2580 (@thinktwice2580)
► Instagram: / thinktwice_ltu
(@thinktwice_ltu)
-----------------------------------------------------------------------------------------------------------
Contact me:
► thinktwiceask@gmail.com
-----------------------------------------------------------------------------------------------------------
🎵 Music by : Jonkyoto - www.fiverr.com/jonkyoto
![Polygon Triangulation [1] - Overview of Ear Clipping](http://i.ytimg.com/vi/QAdfkylpYwc/mqdefault.jpg)
In the next video we will use this theorem together with the theorem proven in the previous video to prove Euler's polyhedron formula: V−E+F=2
p.s. I hope that everyone is doing well during these unusual times. Stay safe.
I love your videos! They're always interesting and beautifully animated. How do you animate them so well?
@@luciuscaeciliuslucundus3647 yeah this is a nice question
Can't wait for the next video. Hope you're doing well too.
Excellent video as always!
👏 👏 ☺
Suggestion:
We can prove this same theorem with topology:
An irregular polygon with n vertices is homeomorphic with a regular polygon with n vertices.
Thus, we morph the irregular poly into a regular one, then we triangulate it and finally we morph the triangulated poly back into it's original shape.
what about triangulation of circles
This is one rule of geometry that seems pretty intuitive
Sometimes it's nice to see the proof of an obvious fact just to realize how unobvious it really is.
Mikołaj Kuziuk Obvious facts are often the hardest to prove
It's kind of obvious in that it's intuitive.
Sometimes what looks obvious proves to be just wrong or impossible to prove/prove wrong, such an elusive thing
@@pleaseenteraname4824 in life in general
Exactly!! Yesterday I saw someone saying on a tiktok comment that they didn’t understand why a n-polygon could be divided into n-2 triangles. And there were so many people just saying “it’s obvious, duh”. And yeah, it looks obvious at first, but how do you know for sure?
Brilliant!
You need one more thing:
demonstrate that for every polygon there exists at least one convex vertex!
Otherwise, you can't prove that every polygon has a diagonal..
Yes, you are right. However I thought it was quite intuitive.
I think you should add a second base case then: if there’s a polygon without at least one convex vertex, then it’s either a triangle or a square. You proved how a S(n) is trivially true for a triangle, now prove how it’s true for a square.
@@nerdporkspass1m1st78 A square? Do you mean a quadrilater? Also a polygon without at least one convex vertex does not exist.
1) The angles of an n-gon always add up to 180n-360 degrees. (This also needs to be proved, but I'm not gonna.)
2) If there were an n-gon where each angle is at least 180°, then its angles would add to >=180n > 180n-360. But this contradicts (1), so such a polygon cannot exist.
@@Quasarbooster in order to prove the sum of angles in a n-gon is 180n-360, you need to triangulate that n-gon into n-2 triangles, which is the thing we ultimately want to prove
Could you also prove it more intuitively like this:
1. Prove that every polygon with more than 3 vertices has a diagonal.
2. The diagonal divides the polygon into smaller polygons that either have diagonals or are triangles. Therefore every polygon can be triangulated.
3. Let P be a triangulated polygon with n triangles.
4. Paint one of the triangles. Now the painted polygon has 3 vertices.
5. Paint a triangle that's adjacent to the painted polygon. This adds 1 vertex.
6. When all triangles are painted, there are n+2 vertices in the painted polygon.
Nuoska This was the proof I was taught when I first learned this.
Hah i thought of the same thing
This is way easier to follow thx
I remember when these videos had almost no words.
To be fair, it's hard to explain a proof by induction without words.
Yes.. whenever I make a video I always try to think of a way to use the least amount of text as possible while keeping everything understandable. It's hard to find this balance. I would love to keep all of my videos wordless but I'm afraid that some topics would just lose their point without any text.
I had a homework during the quarantine for Discret Mathematics and this was literally the first question out of five. Glad I prove it the same way as this video, now I know that I have at least one question right!
Incredibly late to the party, but great video as always! In fact, the number of ways any polygon can be triangulated like that is described by Catalan numbers, which is crucial in combinatorics!
Thanks!!
Amazing, induction is such a beautiful proof technique, especially when it's applied to geometry!
Your animations are just awesome mann!!!😍
Keep up the good work!👌👍
Wow eto tlga pinakaayw ko na geometry
Wonderfully structured/animated/presented!
Interesting, soothing and very well explained. Thanks
Great as always!! Thank you!
Thanks for watching:)
Great visualization and explanation, congratz
that was less trivial than I expected, thank you!
thank you, this annumation make every thing clear to me
What software do you use for the animations?
6:03 What does the arrow represent? S(3) "goes to" S(4)? I don't understand this video. :(
The arrow means implies. So S(3) implies S(4) and so on
It means "S(3) is true" implies "S(4) is true".
This was incredibly satisfying to watch
thank you, this animations make every thing clear to me
I love your proof and so I'd like to share my own. It's fairly simple.
1) Each edge of an n-gon can form the base of a triangle.
2) All n-gons must be bounded
Combining these two facts, the n-gon will fit one triangle for each of its sides, but because the polygon must be bounded, this will require two binding triangles that are on the outer edge. The two binding triangles have an exposed base but also a free and unshared edge. Thus, the number of triangles composing the polygon = N-2. That is, number of outer edges - 2 binding edges.
Great video!
Love Your Videos!
Thanks:>
This is true art!!!
next video : some cool applications of triangulation in math
I'll make sure to cover it in one of my future videos:)
Which software do you use to animate all this, I would like to learn some basic animation in this quarantine time. Plz any suggestions.
Question, how do we know that every polygon has at least one convex vertex ( I assume that is a vertex that has an angle < 180 with its neighbouring sides?) in the first place, so that the diagonal algorithm can work?
Came here to understand the concept triangulation as there is a dynamic programming problem on Leetcode related to this concept. And I wanted the proof why n-2 triangles. Now I’m satisfied so that I can try the problem.
What to say, I just love to wait for such videos to come to my recommendation.
Happy to hear that:)
brillant content, thanks a lot for the share it
Thanks for watching:)
Always waiting for you👌👌.......stay healthy and dafe
Safe
Thank you
Upload regularly or else I'll die
Brilliant!
Do you use Processing and/or After Effects for these animations?
Ok it's Cinema 4d then. Do you have any links to resources to animate?
Awesome.
Thanks for this amazing video. I could write this algorithm in C to support triangulation of OBJ files in my 3d-ascii-viewer program.
There are more efficient algorithms in literature but this one I could understand.
Which software do you use??
how do you define that which side of angle between xz and xy you are checking, yes inward angle is less that 180 but the outward angle definiately is more that 180, how do you choose which side to pick!? 1:53
Hello😁 I love your content, may I ask how you animate your videos
Hey, thanks! I use Cinema4d and processing. I am thinking of making some tutorials but still need some time to plan it out.
@@ThinkTwiceLtu 😁cool
Hey try checking Indian prmo rmo inmo etc geometry n try uploading vedios related to the topics coming in those paper
I LOVE the music!
What kind of keyword should I enter to get more music like this? probably "lofi something", but I can never get something like this...
Thanks for your help!
You may try searching calm lofi, or chill lofi beat. Should definitely find something similar:) Although sometimes it takes a while to find just the right one.
спасибо за видео ролик. очень интересно
Very well explained! I realized that the proof is done by using strong induction (not very common in youtube videos I suppose haha).
By the way, I have been learning plane geometry at university in a completely axiomatic approach (set theory based) and I cannot think in proving 2:12 claim without my book's axioms (in essence they are very similar to Euclid's postulates, but there are more general (results still work in other metric spaces satisfying the axioms) and they are much more subtle). How would you prove it?
I didn't spot the issue Antonio Lewis pointed out (existence of convex vertices in every polygon) at first, but I will try to prove it as well because it is a good exercise for preparing the incoming test haha.
Other thing, in 1:32: isn't that the definition of an interior diagonal? I thought a diagonal of a polygon was a segment joining two non-adjacent vertices.
Good to see a new video and excited for seeing your next one. I hope you are doing well!
Take care.
Thanks! Glad you enjoyed the video. I'm not sure what exactly you are trying to prove from 2:12? As for the existance of a convex vertex, I thought it was quite intuitive so I didn't feel the need to include a proof for it. And yes you are right it's an interior diagonal to be exact.
By the way what book are you using for the class you've mentioned, I'd be happy to check it out.
Thanks for watching, take care:)
@@ThinkTwiceLtu I'm sure you would like it but unfortunately it is written in Spanish. However, I have translated to English the planar axioms and first definitions. You can download it here if you want (I hope I don't get into trouble) : mega.nz/file/7LpgWQbA#4OlW0IU2HV163ZFVF26cnk6GdymtOWWPyNPJvFbjBYE
If you want to see the translated axioms: www.mathcha.io/editor/zmqDdtElSdyh53d2ljSJJYE5uekYYpoHMMpYPy
In 2:12 what I am trying to prove is that: (very informally)
"If a segment connecting two non-adjacent vertices does not lie entirely in the interior of the polygon, then it must be the case that there is at least one vertex of the polygon in the interior of the new polygon formed by the diagonal"
(More formally but not 100% rigorous)
"Let P be a polygon and V={A,B,C,...,N} its vertices (not meant to be 14 vertices, it is an arbitrary finite set). Let X,Y,Z be in V and such that X and Z are non-adjacent. If segment XZ is not a subset of interior(P), then it must be the case that there is at least one vertex of P in the interior of the new polygon P' which is formed by the diagonal XZ and removing the least amount of vertices from P"
The thing is that there are a lot of obvious facts that are tricky to actually prove using the book's axioms, but it feels very good since everything is justified and the prerequisites are just set theory notions (nothing about linear algebra nor analysis) and the very basics of group theory. For example, the "Pasch axiom" is a fact that cannot be derived with Euclid's postulates but with the book's axiomatic system it is not an axiom anymore (well, I think it is equivalent to an axiom, that would make sense).
I have a plan: since I haven't seen the exact same axioms outside the book, I want to translate it for more people in order to people to get introduced to rigorous axiomatic planar geometry. The book doesn't cover very far, like for example the conic curves are missing, but it has a nice chapter on hyperbolic geometry. I would like to expand the book and make it more complete, since geometry is very, very vast and it is a shame that it doesn't get unified with book's axioms.
Note: at the final chapters, it is proven Euler's Polyhedron formula with other axioms (axioms for 3D space geometry), maybe you want to check the proof (?)
Thanks for your reply, I hope you enjoy reading the axioms and taking a glance at the book!
Hey how can you do so much of creativity on the screen you use some application for the drawings and structure
Biggest fan want answer
Pls answer
Perfect
what programs do you use for image animation
?
Used Cinema4d for this one
This really helped me in understanding what ear is in triangulation of a polygon. But I'm still left with one confusion which I'm unable to understand and is out of what it is explained in video and the question is about the concept of non-overlapping of ears.
Wouldn't it be easier to demonstrate that a polygon is a cycle graph and that because each vertex has degree 2 it can have at most degree n (where n is the number of vertices), thus subdividing the original polygon in n-2 triagles?
Just curious, maybe my reasoning is wrong but I think this is a quite more intuitive demonstration.
Which software is being used to make this video
I really love induction
I always loved math including geometry
So is the why the way computers calculate any representation of a 3D object/environment is with everything being made out of triangles?
Yes, and because the surface of a plane between any 3 points in 3D space (a triangle) is always flat, unlike with more (4 points might make a saddle shape). Triangles are also easy to rasterise, which is the process of turning shapes into pixel images.
The 3 points of a triangle always lie on a single plane. It is the most 'basic' 3d geometry, which can help with computing surfaces (lighting/shadows). Also, GPUs tend to be optimized for triangulated meshes. Another method of modeling an object is using 'quads' (4 points per face), which can help with subdivision of the surface (to make it smoother). But these are often still triangulated before the final render.
Couldn't you triangulate a polygon into less than n-2 triangles if the diagonal between two points was colinear with a segment from the polygon? It could still technically be triangulated into n-2 triangles in a different configuration, but it wouldn't necessarily be always the only option.
Also, I would appreciate a less inductive approach, since a self-confirming statement isn't necessarily a true statement. There surely are better ways to precisely explain this phenomenon.
Love your videos and their format, keep it up!
Addressing the colinearity point:
Let vertices a, b and c be the colinear vertices of the polygon with b between a and c. If in your triangulation one of your triangles uses vertices a and c, you would still need a triangle that uses vertex b because otherwise the polygon isn't triangulated fully and consists of an atleast four-sided "uninterrupted" region. And thus you'll be forced to add more triangles.
@@aditya95sriram That seems logical. However, it's not considered in this video's definition of triangulation. I would like a video in this comfortable format with a more in-depth explanation.
Thanks for explaining how Blender 3D triangulates my polygons xD
I believe blender uses the ear-clipping algorithm by default.
What about complex quadrilateral
Last time I was this early, the Big Bang hasn't occurred yet.
(\____/)
( ͡ ͡° ͜ ʖ ͡ ͡°)
\╭☞ \╭☞⠀
4:14 I'm confused as to where x came from or what it represents.
x is a new variable introduced at that point. it can take values between 3 and n-1. That's just a fancy way of saying "let's assume S(3),S(4),...,S(n-1) are ALL true"
@@Flo-rj8tz _That's just a fancy way of saying "let's assume S(3),S(4),...,S(n-1) are ALL true"_
Ok, but then why use a new variable at all? Why not just continue using n to represent those numbers? Now you have to prove S(x) is true just as you did S(n). We assumed S(x) was true but it seems to me that was never proven except for when x=3? Why not just start by assuming S(n) is true? I have so many questions.
n is a fixed number
x is a variable that can take values from 3 up to n-1
the difference, again, being that S(n) is the one that you're interested in, and S(x) is a way to write all that you know in a few symbols.
At that point of the video we are not sure yet that it works every time, BUT it is shown that IF it works for every number before the fixed n (symbolically represented with x) then it must work for n itself, too.
6:03 is when we sum up everything we know.
[1] We are not sure that S(n) works always, but the know that IF it did for every number between 3 and n, then it must work for S(n)
[2] With S(3) being true is the starting point we need to start unraveling all this. Like domino pieces.
Below on the screen, we are just accumulating what we know:
>because of statement [2], S(3) works. There are no more numbers between 3 and 4, so using statement [1], S(4) is true too.
>S(3) and S(4) work, and as there are no more numbers below 5, then S(5) is true.
>...and so on, being true for every integer higher than 3
Early gang present!
Welcome:)
0:42 None of those is the Delauney triangulation :)
Dear Sirs, you have just found one diagonal for a polygon that you picked, but you have not proved that there are at least one diagonal for any polygons. That fact that you found diagonal XV for the polygon shown would not imply you can do the same for an infinite number of possible polygons. Please kindly clarify.
Best regards, David Leung
How you make your video
Just up to release of unreal engine 5
how does he make these videos?
The only videos I don't watch on x2 speed!
Prove that polygons divide the plane in an inside region and an outside please. And if there is an elementary proof generalization to arbitrary dimensional polytopes.
I am early... Quarantine gang
Can a polygon ever be triangulated into a different number of triangles, or is n-2 the only possible solution?
Well that is what this video proves: *any* triangulation of a polygon on n vertices consists of n-2 triangles. So the answer to your question is no.
@@aditya95sriram Ah, you're right. It was presented as a constructive proof that there exists at least one n-2 triangulation for every polygon. It would have been interesting to note that it was a general description of *any* triangulation.
graphics programmers love traingles ,😁😆
Hey, here's a small suggestion. Could you make the music sound decent when played at 2x? It's rather unpleasant
That's RUclips's problem.
@@cornbreadloverrr it's still his problem if that makes me want to watch it less
Better: S(3) true; if S(n) is true then S(n+1) -->> S(n) for all n>3
mind the difference between ordinary and strong induction ;)
Why would anyone pay for brilliant when they could just do through actually rigorous math courses on coursera or just buy some number theory and proof oriented college level books?
There's also some great lectures on youtube. I've recently been watching a playlist on "Lie Groups and Lie Algebras" by the channel XylyXylyX. Also its pretty easy to find academic papers and textbooks online.
Math induction ftw. qed.
Anyone here from codeforces CodeTon?
Wait doesn’t this mean a dot can be triangulated into -1 triangles
Dots aren't polygons
You're ignoring that fact that a point is not a polygon.
_However, assuming your not just trolling, (but we both know you are):_
A line is also not a polygon and using your premise, it would triangulate in to zero triangles. Which makes _some_ sense.
However, a line is also a circle with an infinite radius and infinite sides and would triangulate in to infinite triangles. Which makes _more_ sense.
A circle with a finite radius with infinite side and would triangulate in to infinite triangles. Which makes sense.
So, if a point has -1 triangles, what would -1 triangles mean? How would you interpret this?
I interpret this as meaning a point in 1 dimension short to have any meaningful answer. 😁
I have another way to prove this, but the comment section is too small
Not watching it all, I hate maths
Same
:'(
Thanks for coming to the video just to comment that.