Why the Circle encloses the Largest Area | Explained using Hill Climbing
Vložit
- čas přidán 20. 05. 2024
- We learn why the circle encloses the largest area, compared to other shapes of the same perimeter.
This is my submission to the summer of math exposition:
• Summer of Math Exposit...
Legend mentioned in the video:
worldhistory.us/ancient-histo...
Draw the portal game:
• Doctor Strange portal ...
SunFlower clip:
• Sunflower opening time...
My website:
radufromfinland.com
This actually is a great explanation of why triangles in a circle are always right angled.
Glad to hear this video had many uses :-)
Excellent! So you proved that, for a finite number of points, applying a series of incremental improvements always leads to a regular polygon. Because the number of points doesn't matter it leads, at least intuitively, to talk about circles. Now, I reckon there's still one thing that needs proof and is that a circle is not a local maximum. Maybe there are other incremental improvements that lead to another better maximum… of course there are not, but how to prove it. (I'm not suggesting the video is incomplete or something like this, on the contrary, the video provides excellent tools to think about the problem!)
I'm glad you liked the video. Yes... I left out the generalization to polygon with infinite sides. I had some recorded part for it but found it unnecessary.
And yes, I'm not quite happy with my explanation of 'why the final local maximum is the global maximum'. But here is a proof by contradiction: Let us assume there exists a shape with a larger area than the circle. Since this shape is not a circle, it means at least one angle is not 90 degrees, so applying the final operator we find a shape with an even larger area. Repeating as many times as necessary, we eventually end up at the circle, so the presumed 'better shape' does not exist.
@@Radu I think the last part shouldn't be there. If the initial shape is a polygon, you can't do that with a finite number of moves. But to prove that a circle is the best option, you don't need that; it's enough to prove that every other option has a better alternative
@@Radu But that assumes there exists a shape with a maximum area though. Maybe you can build shapes of ever-increasing areas?
@@momom6197 It feels like this should be relatively easy to remedy by noting that there is an upper bound for the area of any shape of a given perimeter (for instance, the area of the square with sidelengths of half the perimeter). Hence there must be a maximum value (possibly asymptotic) for the area that can be reached. I think that one really needs a limit argument in the end to tie up some loose ends here, but even though I haven't really spent too much time dwelling on it it doesn't feel like it should be too difficult to do this (it probably has to do with showing that for every shape we can apply the procedures a finite number of times to be able to completely encircle the resulting shape inside of a circle of radius (the radius we know gives the maximum+an arbitrary positive epsilon). Then we get an upper bound, and can probably use some squeeze theorem to finish things off nicely...)
Compiling all the arguments in the replies and adding my own, here's a (hopefully foolproof) proof of why the circle is not just a local maximum.
Let's make a few assumptions : The shape is a connected loop with perimeter 1, sitting on a flat euclidean plane. None of that torus or hyperbolic plane stuff, we're going strictly euclidean.
First, let's show that the area is bounded. Since the shape is a connected loop, there can't be a sudden "jump" in space, and there has to be two paths between any two points, adding to the perimeter itself. Therefore, the length of the shape between two points is at least the distance between them. For example, if we take two points with distance 0.2, then the shape's two paths can have length 0.4 and 0.6, or 0.3 and 0.7, maybe even 0.2 and 0.8, but not 0.1 and 0.9, since that would mean the shape found a path between the two points shorter than a straight line. Let's assume there exists two points with distance strictly greater than 1/2. This means both paths taken by the shape between the two points have to be strictly bigger than 1/2. However, that would means the sum of the paths, equal to the perimeter, is strictly greater than (1/2) + (1/2) = 1. The perimeter can't be strictly greater than itself, therefore our assumption is wrong, there can't be two points with distance greater than 1/2 on this shape.
Let's pick a random point on this shape, and create a circle with radius equal to 1/2. Since the distance between any two points can't exceed one half, this circle contains every other point, and therefore the area enclosed by the shape has to be smaller than the area of that circle. To be easier (since we only care about the fact that it's bounded, not the bound itself) let's consider the circumscribed square of that circle, with side length equal to the diameter (1) and area 1² = 1. This means the area of any shape is smaller than 1.
Showing that the circle is a local maximum at all has been done in the video, so we're going to skip that.
Now let's show that there is a global maximum. Let's say there isn't, and that there's a sequence of shapes that gets better and better asymptotically. Since having greater area is an order relation, the sequence of their areas is monotonically increasing, and since it's bounded, it converges. And since euclidean space is complete, the sequence of shapes must converge as well. Therefore, any sequence of shapes with monotonically increasing areas has to converge towards another shape, a local maximum. With the same argument, the sequence of all local maximums must also converge towards a global maximum.
Finally, let's show that this global maximum is the circle. Again, let's say it's not, and that the global maximum isn't a circle. This means you can find a set of opposite points (where both paths have length 1/2) and a third point where the angle at that third point is not a right angle. If you couldn't find such an arrangement, then the shape would have to be a circle. This arrangement isn't optimal, since you can "rotate" both parts to make a right angle and get a shape with higher area. This means the shape we found isn't a global maximum, contradicting our earlier hypothesis. Therefore, finally, the global maximum has to be a circle.
Always a joy to see intuitive or otherwise early taught concepts being proven in understandable ways
Happy to hear :-)
It’s not a valid proof even, without showing the existence. This method has been figured out long ago, and its flaw (lack of the proof of existence) is known ever since. Please include information in your video, otherwise it’s totally false information.
@@atussentinel It's funny how some people in the comments think this proof is incomplete (like you) and some think it is completely unnecessary (like, of course it is a circle). I think it's good, it shows people need to be convinced differently. I pointed out some document that includes a section on existence. If you think it's sufficient or can find a better one (or make one yourself), I will include it in the video description (plan to add some more links there as well).
Let me know if you find videos like this interesting. I can make more 🙂
This tricks was so amazing and the animation made it to the next level. Please teach more! Btw how do u animate?
The app I built where you can play with the shapes (from my website) has built-in animations that I coded my self. Making the video was just recording the screen from there and stitching some things together. Really easy after I coded the thing... I might make a tutorial on this someday, but the code is currently a mess since I didn't really know where I'm going with this in the beginning.
@@Radu I think great softwares start from a mess!
Hey @Radu if u can make a tutorial or a video on how to make charts using JS , I would really appreciate it
@@vijayserpentj7910 I will. Probably soon.
That was so interesting! THe way all the operations come together in the end! We all knew the circle has the largest area, but not WHY it does. hehe another nice one Radu!
Glad you liked it :-)
I like how the constraints (convex > concave, reflectional symmetry for all beads, maximizing the area of the triangle in an arc) ends up describing the circle at the end! But it's still not immediately apparent that the circle is the largest possible area from this explaination to me. If I'm not mistaken, doesn't hill climbing only guarentee that you reach _a_ maximum, but not necessarily the global maximum? I'm not sure how you would go about proving that the circle _is_ the global maximum only through hill climbing.
Hill climbing stops at a local optimum and there is usually no way to tell if it is the global optimum or not (maximum in this case). But for this particular case, using the third operator, we always reach the same outcome: an equilateral polygon (beads have the same size) with all internal angles (90 degrees), so, a circle, because of property where in a right triangle, the median from the right angle is half the hypotenuse. I also think my explanation in the end is a bit fuzzy... and I think I understand your comment. You're saying something like "Ok, you end up at the circle, but how do I know something better is not out there? Maybe another operator could go even higher somehow?". And my reasoning here is that it can't, because if we end up at some other shape, the last operator I showed will notice an angle that is not 90 degrees and it will adjust that one, increasing the area at the same time. So... it's a proof through contradiction. The area you speculate to exist cannot be the largest area. Hope this helps :-) and thanks for watching!
Is because any shape that claims to be maximum area would have to be invariant through the last operator, meaning that it has to be a circle (any shape invariant through the last operator is a circle for sure)
@@gabrielbarrantes6946i like that. Brief but precise.
so I was like "Yeah, integrate and find the maximum" and you went with much different approach. I liked it! it wasn't easier or more elegant but it was unique and made me thought of this as more of a discrete problem.
Wow, happy to hear you thought it was good :-) I was quite sure that those comfortable with calculus will find this other approach boring, but looks like I was wrong.
how could we do it using integration? like keeping the perimeter same and maximize the "area" using maxima and minima concepts?
@@selfxironCodesmaybe yes,because I was thinking the same too
@@RaduI know calculus at heart, but your approach is more novel than the streamlined approach using integration.
@@Diaming787 not novel, though... these kinds of operations have been known for centuries. Only 'novel' thing may be demonstrating hill-climbing in this context and the presentation itself.
That's very clear, the animations are smooth and you do not speak too fast or too slow ! You earned my vote for the peer review !
Thank you :-)
Amazing video as always Radu! I will always be grateful for the LAMAD and LAMI courses back in 2019 :) ^_^
Glad to hear :-) Thanks for watching!
Interesting! I always learn something from your channel, thanks Radu!
Glad to hear that!
I never thought about it that way. Really cool video, I like your style and explanation. This is a very interesting idea!
Happy to hear that :-)
That's really cool! This is a great topic choice for the visual medium, yes the proof is informal but the understanding comes so naturally when we can see it like this
Glad you thought so :-) I'm actually wondering now about the words formal / informal and would like to know what you mean by it. I also agree this is informal, because I'm used to math that is written down following some kind of convention... But maybe that's not quite right.
@@Radu Yeah, I said it was informal because it's visually clear why the process must terminate and we get a circle, but to rigorously spell that out might take some work. Or maybe not, I'm not sure; the only 'formal' proof I've seen uses Green's theorem and some inequality theorems like Cauchy-Schwarz and AM-GM.
@@johnchessant3012 Right, ok, thanks :-) I'm also showing an equilateral polygon all the time and expect the viewers to generalize this by themselves.
Amazing video Radu! You’re a gifted teacher! 🤞
Thanks Tania :-) hope you are well!
Bravo! A pleasure to watch and has earned my subscription. The beginning was down a different path of a well known math coolness that merits its on refreshing video.
Thanks! I'll see if I expand on that intro one day :-)
Excellent video. I found your channel by the self-driving car video on fcc. Loving your content! Many thanks Radu!
Welcome. Thanks for watching :-)
That was a really amazing video addressing something I never even considered before. Very cool!
Thank you :-)
LOVE IT
SoME is the best thing to ever happen to learning hands down. So many people got into teaching math through this, and there are so many new math channels it is wonderful.
It's probably the best competition I've participated in. I think it's because of the mentality and spirit of those who attend.
impressive and intuitive. Thank you
Glad you liked it!
I was so amazed to see the trick!
Awesome, you should teach more tricks like this!
Should I start a channel about magic? :-))
@@Radu Thats cool idea but you may have to double work!
@@sharmarahul384 Maybe I need to revive this series :-)) czcams.com/video/e3MkGisZXTc/video.html
intetesting video and good luck Radu!
Thanks :-)
What an awesome video During my college days our maths professor showed us how with the help of integration, maxima and minima we can solve many issues such as shape which can fit maximum spheres, maximum number of coin that can fit in a polygon etc. This has helped me in critical thinking
Wow, that's great :-)
This is an awesome video!
Glad you liked it
Wow this is a very good video for an intuitive understanding of a circle. Amazing!
Glad you think so!
well done, I like how you are able to easily explain why the circle is the optimal shape without using an calculus. It is very intuitive and very well explained.
Glad it was helpful!
it was interesting, i have been in a slump but have been picking my self up. I am going back to your video's, thanks for uploading and keeping me motivated.
I have to say, I'm feeling the same... Somehow no motivation at the moment. I forced myself to make this video, thinking the deadline will get me going, and it did, but now that it's over I'm procrastinating again :-) Luckily I have some content to publish until October.
Awesome man! you made me learn somethin while actually being interested.
Glad to hear :-)
Wow! I was expecting something very simple, but your explanation was brilliant and illustrated AMAZING topics!! The idea of "higher dimensional hills" reminds me GREATLY of the gradient descent in neural network learning, I would love for you to post a more in-depth explanation about how higher-dimensional gradient descent applies to a random variable (the initial condition of the beads, which could be defined with a chain of normal variables with heavy boundary conditions). That's a hell of a combination, though, discrete math and vector calculus and probability theory. Still, sounds pretty nifty to me:)
Glad you liked it :-)
I might do more in-depth math explanations, but my channel focus is more on algorithms and programming, so it may take a while. But who knows... I reprioritize things all the time!
Thx for your videos!
You're warmly welcome!
This made me smile from minute one - loved it!
PS Good luck!
Great to hear :-)
Nice video!
Thank you.
Wonderful explanation
Thank you!
Absolutely beautiful!
Thanks!
Incredible animations.
Thank you!
I'm so glad I clicked in this vid
so well done!
Thank you :-)
Nice work
Thanks
Fascinating!
It is :-)
So fun! I loved this!
Happy to hear :-)
You could have just stared with concave angles in shapes always leading to them being smaller, then finished by starting with a equilateral triangle and adding more points to keep getting bigger equilateral shapes (square, pentagon, hexagon) which leads to a circle.
You can probably arrive to the same conclusion in this way as well, but need to demonstrate somehow that equilateral shapes are better. And that increasing the number of sides is better. Intuitively the explanation makes sense, but there are some holes that need to be filled :-)
I don't know if you won or not but this was amazing. Really like your way of explaining things.
I did get an honorable mention :-) thanks for watching!
Man, the step by step approach was beautiful
Glad you liked it :-)
Great vid!
Thanks!
Soap bubbles. Lowest energy state. Science words. Proof. Thanks!
Sorry, don't know much about this topic :-|
Loved it!
Glad to hear!
Thank you so much sir!!! This was a very useful fact:)
Glad it was helpful!
@@Radu 😁😁
Very simple to follow thank you
You're welcome :-)
Found a way to break the "maximum area" on your site lol
Nonetheless great proof/vid! You have my sub!
🤯🤯! Thanks :-)
2:22 sick transition
Thanks :-)
Very fun rigorous math!
Thanks :-)
This was really fun to watch! As an educational video creator myself, I understand how much effort must have been put into this. Liked and subscribed, always enjoy supporting fellow small creators :)
Thanks for the nice comment :-) I checked your channel briefly and it looks awesome! Amazing how many small channels with quality rivaling large ones exist. Subscribed and will have a closer look when time.
Haha, I was able to cut a hole is a fairly small piece of paper, and wriggle myself through it. An excellent question, and excercise, for any birthday party.
Cool :-) yeah! It can be surprising to people.
Loved the fact you solved it by hill climbing. Hmm, I wonder how a neural net would get on with it.
Imagine if AI somehow finds an even better shape 🤯
This is excellent thank you! Two questions: 1) can it be shown that each of the three optimization motions are independently necessary? E.g. does enforcing the "right angle all around" rule THEREBY result in satisfying the "copy biggest half over symmetry line" rule? And 2) in the end, the logic here appears to be "circle maximizes area because right angle maximizes triangle area - so you've reduced the former problem to the latter, but without proving the latter. Is that right?
1) Actually, the third optimization technique is enough, I think, assuming you always apply it on the 'better half'. It will always increase the area by a bit at each step. The reason I taught the other two techniques is to give an idea of different operators and to cleanup the configuration when applying the third one. I mean... if it would not be convex, the beads may end up crossing the triangle making things look... not so great
2) I'm not sure I understand this. Maybe you have former and latter mixed up?
Great work
Thanks!
Very enjoyable :)
Glad you think so!
sir please make game development videos (if I really love something in my life, it is game development).Btw this video is also very nice.
nice to see you are getting more and more subscribers. keep growing sir .A lot to learn from you about programming.
I have a plan for game-related content, but it might take some time to get to that. Please be patient :-)
It is important to note that this line of reasoning only proves “If there exists a shape of maximal area, then that shape is a circle.” It does not actually prove that such a maximal shape exists, only that non-circles are not maximal. To see why this matters, consider a similar argument for finding the largest positive integer:
“For any positive integer n, if n is not equal to 1, then n*n is larger than n, which means n is not the largest. Therefore, none of the positive integers except 1 could possibly be the largest.”
This corresponds to what you have shown with areas: none of the shapes except a circle could possibly be the largest. As it happens, a circle *is* the largest shape, and 1 is *not* the largest positive integer. Simply showing “No other option except this one could possibly be the largest” is not sufficient. You still need to prove existence.
Sure. My goal was to give some intuition. I'm sure there are other people who can formulate riguros proofs for those who need them.
Does this apply to higher dimensional objects too? Like some weird 3d shapes into sphere
I think so. Spheres and hyperspheres in 4D and beyond.
It looks great! The only thing that you would be missing is a proof on why no other shape other than the circle can have the same area or greater.
It's not necessary. By showing that the triangles formed between the two beads on opposite sides of the shape and the third shape has a maximum area when a right angle is formed, he's shown that the largest shape must be formed with all of these triangles being right. This implies that no other shape could possibly have a greater area. Also, no shape could have the same area unless it was possible to make the bead triangles have the same area, but with different angles, which is not. He showed that visually.
The algebraic reason is that the area of a triangle is abSin(c)/2, which is maximized when c=90 degrees. However, the point of mathematical CZcams is to show all of the beautiful relationships visually without bogging everyone down with the esoteric details that can easily be visualized.
Thanks for the detailed explanation. It is exactly what I had in mind!
Very interesting approach, but what's kind of missing for me is to show that the circle is the *only* shape that can't be improved by these operators anymore, i.e. that fulfills the respective criteria
You're not the only one that isn't convinced :-)
in the simulation you have if you scrunch up the beads into a beed pile and iterate your beads well spread apart making the circle really large
Yeah, I've noticed there are are some bugs that appear when an operator moves the beads creating some overlap. The physics try to resolve the overlap and it does it by causing this glitch :-P I couldn't find an easy fix.
@@Radu honestly really don't care about bugs unless they break the program and that bug is kind cool
:-))
I like how this video shows different ways to transform a figure to another with the same perimeter but larger area. The only part I have a question on is how do you know that all the hypotenuses converge to the same length.
I tried to save your video in a playlist, but that option is not available! Why is that?
I don't think it would be possible for hypotenuses to not have the same length. I mean, it would mean that the points are on 2 different circles somehow (if all are indeed hypotenuses in right triangles). Maybe if you have some kind of star-like shape it would work... but then it has concavities, so the first operator would work again. (not sure if I answered your question or if you understood what I meant... some things are hard to explain in the comments)
PS: There's nothing special about the video, I think. You should be able to save it in a playlist.
I first learned about this wonderful proof from What is Mathematics by Courant and Robbins.
Really? Just how similar is it? Would it be possible to share that proof somehow? (maybe on the Discord linked on my channel banner?) If it is more rigorous than mine and touches on he continuous aspect, I could link it in my video somehow.
@@Radu You've done a great job here, sir. But I find it highly unlikely that you haven't seen that proof already. This is just a CZcams rendition of that proof bit by bit. Check out "Steiner's proof of isoperimetric problem"
I don't have the book but I googled Steiner's proof and found some people explaining it. It is AMAZINGLY similar indeed, apart from me using the hill climbing approach. All I can say is that I haven't seen this proof before but I was familiar with many of the techniques from other places (learned them when doing research on the traveling salesman problem and vehicle routing problems).
I can definitely see how you don't believe me :-D and it's ok, I don't mind, but in case you're curious, here's how the video developed: in my first draft I didn't have the first 2 operators (moves) at all. I just had the scissoring, but with the condition that the angle we select must be from a 'better half', otherwise, there's a possibility to go downhill. Problem was I didn't like the animations (specifically, the triangle I show for the third operator was not clear, because the shape was not necessarily convex and the contour would sometimes cross the triangle and make areas harder to understand - concept of a region with negative area also appeared...). Then, I added the first operator to guarantee that we have a convex shape and then the scissoring animation looked good after that. Video was almost left in that state, but I had some time until the competition deadline, so I gave it more thought. I thought that since we have 2 operators already, it might be good to add a third one to better illustrate what local search is about. I wanted one that complements the first but doesn't immediately solve the problem. I first came up with something that stretches / squishes diametrically opposite points depending on the average distance between all other opposing points. It worked well, but it was too good (ended up to the circle again). I then switched to almost the same as now, but instead of just mirroring, it was also flipped so that the configuration on one half continued in the same order on the other half (hope you understand what I mean). The problem with that was that repeating it also lead to a circle (also, I didn't know to explain why :-D)... so, then I noticed that if I simply mirror, it doesn't converge, yet it still complements the first operator. Was just what I was looking for :-) do you believe me now? :-D
I'm a little confused at the end - Your argument is that since the median of a right angled triangle is half the length of a hypotenuse, (let's call this half length R) that implies that this is a circle because the distance from a single point is the same with all of these triangles. However, this only works if we assume that these right triangles have the same area (or at the very least, the hypotenuse is always the same length, and this length is the diameter of the circle), but while this is intuitive visually, analytically I feel like something is missing. Especially since we only see a limited selection of the infinite possible triangles. Who's to say that there isn't some triangle we're missing? Or that one of the hypotenuses is shorter than the other (since the perimeter is made of beads, this may be easy to find since it's not a perfect circle). Or that even if the distance is the same, the length R is not centered at the circle.
Intuitively the proof makes sense, I just can't shake this hole my brain is finding.
Good question. I had to rush the ending so, not surprised you got confused. I'll try to explain here: don't think about hypotenuses (one is enough). The right angle tip is the only one that moves to all other beads, one by one. All those are right triangles with median length R (as you defined it, half the hypotenuse). Hope this helps.
PS: in this discrete example, you can actually show all possible triangles quite easily as I do around 6:22.
You can actually prove it mathematically by using variational calculus in polar coordinates and by putting a Lagrange multiplayer that constraints the length. The equations would give you. r=const
Thank you for pointing this out.
'To the laboratory' I thought it would be Leonard 😂 Really interesting video!
I've thought about it :-)) but I only had 4 days to work on this (the deadline was strict) so, I left out some things like that. This video could have used a few editing passes otherwise as well... But it is what it is :-)
@@Radu 4 days and a quality like that 💯
Thanks :-) I tried my best!
There is another operation that could be helpful, though I don't know whether it would shorten or lengthen the proof. You can cut the shape in two halves so as to halve the circumference, then mirror one of the halves so that it intersects the other half in the same line segment as before, but with inverted orientation. This preserves circumference and area, but it might make the shape non-convex again. In fact, to not make the shape non-convex, the angle at which the secant intersects the circumference must be a right angle everywhere. Does this characterize a circle? If so, two operations do suffice instead of three.
Ok, so similar to the mirroring, but mirror + flip, if I understand correctly. It would work, I think. Let me know if you put it in practice :-)
it's a nice explanation.
but, personally, I prefer another based on one simple fact, it's easy to prove that for the same perimeter, the more sides the regular polygon has, the more area it covers.
you can easily check by manually measuring a triangle, a square, a pentagon and an hexagon.
so, what we need is a polygon with infinite sides. and that's a circle.
Thank you 🙂
As with many things in math, there are many ways to reach the same result.
@@Radu and many ways to explain each solution.
some people will find one way easier, others will find another.
Nice explanation! One thing I wonder though: the third move you describe relies on accepting that a right triangle has the largest area of the possible triangles. But that's just shifting the question from "Why does a circle have max area?" to "Why does a right triangle have max area?" For the other two moves you describe, it's immediately obvious that the move increases the area. But the right triangle thing isn't immediately obvious.
Good point... didn't think of that. Probably because I've known about the triangle fact for a while and used it often in projects. To me it feels as obvious as the others... maybe my animation is not great there either. I think I could have squished / spread the triangle more to clearly emphasize the difference. Will note this down for next time :-) Thanks!
the area of that triangle is a*b*sin(x)/2 where x is the angle between sides a,b. During that "scissor move" a,b are fixed, so the maximum happens when sin(x) maximizes, which is for 90deg. And you don't need to know that the circle has the biggest area for a given circuit to obtain that area formula
@@yennefer415 such a clear answer. Thank you :-)
Subscribed:)
Thanks :-)
@@Radu No problem:)
I study the graph analogue of this problem; given a graph G = (V, E), the goal is to find the subset of vertices X that minimizes the ratio of boundary to area. Since there are many ways to define the boundary and area of such a set, there are at least three different versions of this problem that may all have different solutions for the same graph.
Sounds interesting. Can you give an example of a way to measure boundary and area for such a set? All I can think of are some generalizations of convex hulls or Delaunay triangulations.
@@Radu I took a course in graph theory so I can answer you that: there are the inner boundary (all points in a subgraph that are connected to points not in the subgraph), the outer boundary (all points not in the subgraph connected to the subgraph) and the boundary (all edges between the subgraph and points outside of it)
@@jonathanlevy9635 Precisely; the *vertex boundary* of a set X is the set δX = {u in V: u ~ v for some v in X} and the *edge boundary* is the set ∂X = {u ~ v in E(G): u in X and v not in X}. There are also two definitions of area; for the first, the area of a set X is simply its cardinality, and for the second, the area of a set X is vol(X) = sum of deg(x) for x in X.
Using these definitions, the *vertex expansion* of X is |δX|/|X|, the *edge expansion* vol(∂X)/|X|, and the cheeger constant vol(∂X)/vol(X).
Graph isoperimetric problems are NP hard, but relaxed solutions can easily be found using the spectrum of the Laplacian matrix due to the eigenvectors representing ideal flows of the vertices. The smallest non-zero eigenvalue is useful in particular for partitioning the vertices of a graph into two sets and is commonly used for image segmentation.
Thanks!
Thanks!
I love your videos
Thanks for watching :-)
Wow! Such an elegant proof, and easy to explain to anyone who’s taken a geometry course :)
Thank you :-)
what a great video
Thank you!
Beautiful! But how do you prove that it always converges through these operations?
Well, the last move is the one that converges. Others do not. For the last one, let's assume that we end up at a different configuration with a maximum area (not the circle). In that configuration, we must be able to find at least one angle that is not 90 degrees, otherwise it would be a circle. But if we find such an angle, we can 'scissor' it to be 90 degrees, and increase the area slightly. So, our assumption of another configuration with maximum area existing was wrong.
@@Radu Perfect, thank you!
There’s an old legend in Baltics that Germans came to lands settled by pagans in current Latvia. The Germans wanted to create a small settlement just to get a foothold but the natives were unhappy. Then Germans used a ruse - proposed to take only a land covered by a single animal skin. Natives agreed. Then Germans cut the single skin into a long strip and used it to cover a large area.
Interesting. It's the same as the legend of Carthage (I mentioned it in the beginning, and linked in the description).
Is there a proof that you “cannot” find a 4th operator to further make the area larger? I think not and I think it revolves around “if you do anything, it is the reverse of operator 3 hence it’s smaller”.
I had something like that in the video. That weak claim that if you do something to the circle, the 3rd operator will then activate and can make the area larger. But it's not really a proof.
awesome
Thank you :-)
4:30 It's true that once you reach this sort of figure, with 2 perpendicular axes of symmetry, the mirroring operator won't increase area, but it won't decrease area either. However, do it anyway, on a line off both axes. Because the cut line crosses the figure at an angle not perpendicular to the perimeter, this will create more concavity, so you can continue using the 1st 2 operators. The only way this can stop is if every potential cut line crosses the perimeter at right angles… which is also a circle.
So, you suggest to apply the second operator even if the area stays the same, hoping it will activate the first operator. Interesting :-) I might try it after my holiday.
tanks to you for teach
You're welcome :-)
man your english is really good
Thank you.
The isoperimetric inequality states that for any region of area A and boundary length L one has L^2 > 4 Pi A with equality only for the circle . There are many proofs and extensions of this inequality. It has many applications ,e.g. in partial differential equations .
Thanks for explaining it formally :-)
I knew where the proof was going the moment you introduced the third move, because of Vsauce's video on Thales' theorem :)
Now that you mentioned it, I had to go watch it 🙂
Made me wonder if I should have went all the way to the axioms... I didn't bother proving those statements about the right angle triangle at the end. But I think I wouldn't have met the submission deadline if I did, so, it is what it is.
@@Radu I thought your exposition was excellent! It just goes to show how you’re participating in the worldwide effort of educators to make math accessible, intuitive and engaging. Hopefully my comment will direct more people to Vsauce’s video, and the Algorithm will pick you up by association with a much bigger creator (an actual SEO technique). Keep up your wonderful work!
@@samevans4834 Thanks! And thanks also for the lesson on SEO :-)
I was thinking about this today because I was bored and remembering something from math class, then I got this recommended to me, hmmmmmm.
I've heard people saying things like that when searching for something related or even talking to other people about something. But thinking about some topic, that is new :-)
This guy is a new Vsauce in the making
Oh, I think I'm quite far from that :-) But thanks!
Well, by definition the angle inscribed in a semicircle is 90 degrees. The motions to move to convex is important, though. And then the motion to areawise symmetry. It's as if you're incrementally defining a circle. I guess that makes sense given that a circle is well defined to have such qualities, so I can only imagine the hill (3 dimensions) to be rather simple. I would like to see another shape with a basic quality that would have local maximums, though.
Yes... well, moving to convex or making it symmetric are not really necessary. The third operator would have been enough actually, as long as you always apply it on the 'better half'. But I wanted to demonstrate some other operators that came to mind... I had few other ones as well, but they were more difficult to animate, so I stuck with those.
I'm curious what shape you have in mind :-)
Nice video
Thanks!
I have a question: can't we do that with only the third move?
I think that if you accept the idea of 'negative area' this could actually work. Seems that if you play with the interactive tool (on my website) you can get improvements always when using the third move (operator).
@@markhall2414 I think I can imagine what you mean, some weird shape with some extreme concavity... I think a situation like that can happen, but it wouldn't be a problem. First, even if we talk about 'negative areas' and the result is still some 'negative area' it would be still a larger value after the move, gradually moving towards positive values. And second, that part (with the weird concavity) isn't where the operator would be applied in the first place. You can't have a shape with just concavities, it would likely be applied somewhere where the shape is (at least partly) convex. (Just thoughts, and not entirely sure we're speaking of the same thing, so don't take what I said too seriously :-D)
To me, you're the winner
Glad you liked it :-)
I definitely dont think you need the mirroring or concave->convex transforms. I think the last requirement is sufficient to get a circle. I'd love for a counterexample though
The first two operators can be applied anywhere there is a concavity or a weaker half and they will improve the shape. The third one cannot be applied everywhere there is a right angle. Think about a shape where you have a messy half, where you fix the angle, but the other half is perfect (half circle). Scissoring and mirroring the bad half may decrease the area overall. The scissoring can be enough if always applied on the better half, for example.
Area is proportional to the number of sides, more sides more area
More sides, more area, yes, but I don't think proportional is the proper term. Proportional would mean that there's a constant ratio involved. Like if the perimeter is P and the area of a regular pentagon with perimeter P is A5, and area of a regular hexagon with perimeter P is A6 and the area of a regular heptagon with perimeter P is A7, proportional would mean that A6/A5 = A7/A6 and that is not the case. The ratio decreases (towards 1) as the number of sides increases (towards infinity).
Cool
:-)
This proof shows that if there is a maximum, this is the circle, not that this maximum exists. I can prove 1 is the greatest integer with the same type of proof :
2² > 2, 3² > 3... so 2, 3... aren t the greatest integer cause I have a method to find something greater. But 1² = 1, here the method doesn t give something strictly greater (1 is like the circle here), so if there is a maximum integer it is 1. But I think 1 isnt the maximum of |N*
I like the example, but I would like it even more if 1 wouldn't be the minimum :-D somehow makes it look like (come on, obviously it's not the maximum...). Maybe taking the interval (1, 2) and applying the square root instead? all values lower than 1 increase... if you apply sqrt repeatedly to them you end up at 1 (similar to the local search example). But then values above 1, decrease when applying the square root... (don't know, just thinking out loud).
bruh i smoked a huge bowl last night, fell asleep on youtube and opened my laptop to this
What a great way to wake up, huh? :-D
Small correction: the area of a triangle is the base lenght times the height *times one half*
Wow :-D can't believe I notice it just now. Thank you!
You could have also gone into the main problem with top of the hill algorithms like this: you might get to a peak that is a local maximum, but not the global maximum. This isn't the case here, but you kind of glossed over this, which I think is a missed opportunity
Yes, I agree...
That is something I noticed as well.
I found a bug in your Largest Area app. If you try and spiral up the beads for the starting shape, I managed to get it so that when you use flips, you end up with a shape that crosses over itself, but the shape is not convex, and the app says I can't do any more Flip actions.
Wow :-) interesting... Thanks for pointing out!
I wonder if we can still talk about concave and convex if the polygon is self-intersecting like that, though... What do you think?
@@Radu I feel like if the polygon is self-intersecting, then we'd want to cut it at the points of intersection, then sew it back together in such a way as to remove the intersection. That is, a local X shape maps to a > < shape, which is also concave and able to be pulled apart.
I tried this with beads and water, and discovered that circles don't enclose any area.
:-))
That's the reason why I love Maths, like we can just proove anyhting. It's just so Natural, that if Maths was the Language of Gods.
:-) nice thought
I've been thinking the same thing except with balls. I thought about planets volumes compared to surface area.
Cool :-)
@@Radu Can you make the same video with balls?
@@ncrwadr I don't think I'll make another video like this one, at least not anytime soon :-)
@@Radu Ok.
Interesting. But what about non-euclidean geometry?
Interesting :-) maybe I'll look into it someday!