Hey guys, I published this video and then immediately went to sleep (sorry!), but it was seriously a bunch of fun to program, and I would love to make videos like this some more! Anyway, let me know what you think / I hope you guys are having a wonderful day!
@Keldor3145 жыл бұрын
A random distribution of points! Just what I've always wanted!
@mfaraday40444 жыл бұрын
When I figured out this video , I was legitimately stunned how wonderfully you explained. Thank you Sir My biggest gift for today is that I found this channel
@DrawCuriosity7 жыл бұрын
This video was a gift to my mind! It takes skill to explain three algorithms so well and succinctly as you did, and that's one great gift to have ;)
@LeiosLabs7 жыл бұрын
Haha, you are awesome! =)
@dragoncurveenthusiast6 жыл бұрын
Draw Curiosity nice to see a fellow biologist on this channel! :-)
@MD-ji7dh Жыл бұрын
This dude had an intro a story and still managed to explain 3 algorithms in under 3 minutes. Crazy
@albertwang59746 жыл бұрын
Cool, supper cool!!! we can use these algorithm to improve the efficiency of image object recognition.
@LeiosLabs6 жыл бұрын
Woah! That's cool! I hope it works! =)
@colemanhk4 жыл бұрын
Quick question. For Graham Scan, what does "removing any vertex that points outward" refer to? I think it should be "removing any vertex that points inward". (My understanding inward = points toward the center of the hull; outward= points out from the center of the hull). Thanks
@nishadkumar73227 жыл бұрын
Wowww. You just solved my never ending confusion in 2 minutes. Thanks a lot!! \m/
@LeiosLabs7 жыл бұрын
Visualizations help sometimes! =_
@DeirdreSM5 жыл бұрын
Thank you for the explanation of Graham. I'd understood Jarvis and the Chan approach, but not that step in the middle.
@guilhermegondin1516 жыл бұрын
Nice gift, even more special since it's random, so no one got the same gift as the other (or nearly no one) XD
@LeiosLabs6 жыл бұрын
Haha, I'm glad you liked it!
@KingFredrickVI7 жыл бұрын
I have no idea what this is used for but it seems pretty legit mate lol
@LeiosLabs7 жыл бұрын
Actually, the hulls are used a lot in a number of different places, although it's not obvious where and why. One example is in robotics. The robot has a complicated obstacle course to run through and needs an optimal path around everything. That path will end up being a convex hull around the random points.
@thob7 жыл бұрын
If you can find an outermost point in the set, can't you just then rotate it all in one direction and keep selecting the outermost point until you find the first one again, and then unite them all?
@KingFredrickVI7 жыл бұрын
You'd end up with an infinite turn problem. You'd have to figure out how much to turn. 1 degree? 5 degree? 0.0001 degree? Too little it takes a very long time and too large and you miss 1/2 the points. Not to mention that every time you rotate by, say 0.5 degree, you have to calculate the sin and cos then apply that calculation to every point, every iteration.
@LeiosLabs7 жыл бұрын
Yeah, this is one of the problems, I think. Basically, these algorithms guarantee you will find the convex hull by using a discrete method. Unfortunately, they are not as intuitive as our continuous minds want them to be (which is super cool, when you think about it).
@andywright88036 жыл бұрын
KingFredrickVI Not really. Simply rotate clockwise by say 1 degree. If it doesn't pass another point, rotate by another degree, otherwise if just one point has been crossed, you have located the next point in the wrapping. If you have crossed more than one, go anticlockwise by half a degree etc. Seeing the algorithm considering points in the middle just makes my head hurt and my brain scream that this is so inefficient
@TheFlynCow6 жыл бұрын
And how do you determine if a point has been "crossed"? Also, if a better algorithm is really that simple, do you think the mathematicians mentioned in the video, with multiple awards and honors, couldn't come up with it?
@AmineZyad6 жыл бұрын
Any idea about the complexity of those three methods? I can see from the last example that Graham found the convex hull quicker than the others.
@LeiosLabs6 жыл бұрын
Chan's: O(nlogh) Graham: O(nlogn) Jarvis: O(nh) n -- number of points h -- size of hull Chan's should be faster than both. The animations are not indicative of performance.
@glowiever5 жыл бұрын
What about expanding polytope algorithm?
@DogeisCut6 жыл бұрын
I love these dots!
@LeiosLabs6 жыл бұрын
Woo! I'm glad!
@dhruvarya38917 жыл бұрын
Sweet treat for the brain.
@LeiosLabs7 жыл бұрын
Yeah, I really liked these algorithms! They were super fun to implement!
@zebcode6 жыл бұрын
LOVE THIS! THANK YOU!
@LeiosLabs6 жыл бұрын
This was one of my favorite episodes to make! I'm glad you liked it!
@LeiosLabs4 жыл бұрын
@Michael Darrow Haha, he probably was!
@ethanl98453 жыл бұрын
Very nice
@viforcarry83726 жыл бұрын
I had to do it for on a project, and I found another way to make a convex hull:- join the dots of the min, the max of x and y. - then for each line of the polygon calculate the max distance to it and add it to the polygon. After some iteration, you got the convex hull.
@viforcarry83726 жыл бұрын
After doing some research, I'm not the first to use this method, it's called quickhull and have O(nlogn) efficiency.
@LeiosLabs6 жыл бұрын
Yeah! Quickhull is amazing! We didn't get to it here, but it's definitely on the list for the AAA.
@viforcarry83726 жыл бұрын
The other cool thing is that this method can be generalized in a n-dimension space
@LeiosLabs6 жыл бұрын
But I thought it was tricky for >3D, right? I remember running into it a few days ago for knot theory algorithms...
@viforcarry83726 жыл бұрын
Leiosos, I don't know I didn't test it already
@johnnyboy905286 жыл бұрын
I love it. :3
@LeiosLabs6 жыл бұрын
Thanks! I'll see what other algorithmic gifts I can find lying around...
@punchster2892 жыл бұрын
first algorithm was O(n2) runtime. the scan was O(nlogn). I believe the last one is at best O(n sqrt(n)) and averages to O(nlogn) runtime, but there are ways to get an average O(nsqrt(n)) runtime complexity which is provably the best you can achieve for gift wrapping. Simplest one is divide the region into sqrt(n) sections of sqrt(n) points each. You can do this in n*sqrt(n) time by selecting a random sqrt(n) points via blue noise and using a voronoi diagram to seperate the regions. Then for each of these sqrt(n) regions the problem recurses. Once you get down to regions of 5 points or less, use the scan method to wrap them, then recurse out and wrap again until you've wrapped the full thing. The cost here is n*sqrt(n) for the voronoi seperation. Then everything else after doesn't contribute to runtime complexity. the recursive step adds sqrt(n) * sqrt(n) sqrt(sqrt(n)) which is really n^(5/4), which is less than the n^(3/2) and does not contribute to the runtime complexity. Using the general rule that on average for a collection of n points, the hull surrounding it will contain on average sqrt(n) points (intuition being perimeter vs area), the scan which was before nlogn will now take sqrt(n)logn, which is also less than nlogn and thus doesn't contribute to runtime complexity. There are certainly more effecient ways to impliment giftwrapping with O(nsqrtn) runtime, but this is the simplest one to explain I think
@joulesjams207 жыл бұрын
Why is Chad's algorithm better? Wouldn't it be easier to use Jarvis algorithm as Chad's algorithm has Jarvis algorithm within it
@joulesjams207 жыл бұрын
gustorn but why?
@LeiosLabs7 жыл бұрын
Yeah, I ended up just ignoring the complexity cases. I should make a video explaining them in more depth and then link to that video from now on. I just need a way to make the cases much easier to understand.
@thebetterselfeveryday5 жыл бұрын
Best explanation!!!!!
@Asdayasman6 жыл бұрын
These algorithms do a lot of checking the wrong points... What if you just found the right point first time? Start with the leftmost point, draw a line from it to the top of the space, then rotate it clockwise about the leftmost point by an angle. If there are no points to the left of the line, repeat the rotation. If there are more than one point to the left of the line, divide the angle by 2 and rotate the line about the leftmost point anticlockwise, and repeat the check. If there is exactly one point to the left of the line, that's the right point. Continue on from there, drawing the line with the slope equal to the line drawn from the first point to the second point. There'd probably be some shortcut you could take if multiple points were on the same line of the convex hull. Surely I'm not the first to think of this?
@ThePowerExcess6 жыл бұрын
This won't work on higher dimensions than 2D. Convex hulls problems arise in high dimensional data. This is more of a toy example.
@LeiosLabs6 жыл бұрын
So, that implementation seems to work fine in a physical model, but computationally, it is precisely the same as the Jarvis march (unless I misunderstood).
@Asdayasman6 жыл бұрын
The march is a comprehensive check over every point, right? My method is a search, somewhat akin to a binary search. Someone made the point of higher dimensions being a problem, but I'm not sure I believe that; represent the rotation of the bisection as a matrix instead, and give the bisection n-1 dimensions, where n is the amount of dimensions in the search space. Instead of searching for one point, you'd search for n-1 points, (so a 3D space would have you building a triangle), one at a time. Once you find one point, you rotate around the shape you've built up to that point until you hit the total of n-1, then pick an edge off which to build the next shape and carry on. I'unno, it _feels_ like there's something in this.
@TheFlynCow6 жыл бұрын
The problem lies within determining wether a point is on the "left" or "right" side of the line.
@TebiByyte6 жыл бұрын
What about quickhull?
@LeiosLabs6 жыл бұрын
Oh yeah. Love that one. We intend to put it in the algorithm archive after quicksort.
@LigiaCeballos6 жыл бұрын
thank you TTwTT
@LeiosLabs6 жыл бұрын
your welcome!
@muzharhusain86914 жыл бұрын
Sir ap urdu lecture b provide kr dayn gift wraping
@rhutshab8 ай бұрын
too short
@europetruck58796 жыл бұрын
U desirve a subscribe just for your voice . Plus for explenatin you are giving to us
@LeiosLabs6 жыл бұрын
I am glad you liked the video!
@godofwinetits38264 жыл бұрын
when will you send me my dots?
@MrRudale7 жыл бұрын
Interesting video. When looking at each distribution of random points, people are able to 'wrap' them, so the visual system must be doing some kind of algorithm too. I wonder how the human brain solves this problem, and whether that can be used to make more efficient algorithms.
@LeiosLabs7 жыл бұрын
Actually, I have been wondering something similar. In addition, is there a good machine learning approach to this? It's incredibly interesting to think about!
@goroth016 жыл бұрын
Unfortunately the human brain works fundamentally differently from how a computer does. A CPU is a massively serial processing machine, capable of billions of serial calculations per second, with limited parallel processing. Your brain, on the other hand, has limited serial processing, capable of perhaps 100 calculations per second on a single 'thread,' but makes up for that limitation with a massively parallel processing strategy. With an estimated 100 billion neurons, each firing on average once per second, you get an initial napkin-math estimate of around 100 billion calculations per second across the brain. Your brain has another trick up its sleeve, though. Each neuron can project to thousands of other neurons, and the signal of one neuron can increase or attenuate the signal from other neurons at a single synapse. Therefore each single synapse can also be considered to be a calculation. And there are somewhere on the order of 10^15 (one quadrillion) synapses in the human brain. Furthermore, a CPU is a general-purpose calculator, with algorithms being contained in instructions fed from memory. The brain, on the other hand, has the majority of (known) algorithms stored simply in its circuit architecture. The retina, for instance, has a specifically designed architecture that does much of the initial 'heavy lifting' of visual processing, without the need for any kind of instructions or memory. Therefore, to have a CPU approach a problem the same way the human brain does, it would either have to inefficiently emulate parallel processing (as is the case in neural network algorithms) or have a completely new architecture that emphasizes massive parallel processing.
@ore22366 жыл бұрын
You could use GPUs for the parallel calculation aspect, they're better than CPUs It feels a bit like those linear regression problems, i think neural networks could work fine on this, but i'm not an expert
@b.f.skinner43834 жыл бұрын
Trying to learn convex sets and this really helped with the intuition thanks :)
@the-er1cd3 жыл бұрын
Im somewhat embarrassed about how much I've thought about this problem specifically :)
@suryavaraprasadalla851116 күн бұрын
wonder man thanks
@justwiredme Жыл бұрын
Thank you
@benzeltser98512 жыл бұрын
I love it
@gaboqv2 жыл бұрын
Jarvis algorithm was a little hard to implement, the notion of max angle leads to orientation and lots of nuances that are a little annoying around angles and computing, but I am glad i finally was able to implement it, just so if anyone want to do it too, try to stick to the law of cosines and use clockwise orientation determination to know if you want the inside or outside angle, arctan was a mess
@FaZuQ2 жыл бұрын
Thanks for explaining Chan's algorithm
@personalitymain503410 ай бұрын
Phenomenal video, easy, engaging and to the point !
@sau0025 жыл бұрын
Excellent
@n484l3iehugtil6 жыл бұрын
Can you explain why the hybrid algorithm is faster than either of the two previous algorithms by themselves?
@LeiosLabs6 жыл бұрын
Jarvis March is best when there is a small number of particles, Graham Scan is best when there is a large number, so we use Graham scan when there's a large number of particles so that we can read a small number of particles into the Jarvis March. I hope that makes sense.
@n484l3iehugtil6 жыл бұрын
Thanks for replying. But I wonder why would you want to read a small number of particles into the Jarvis March when you can just solve the problem outright using purely the Graham Scan?
@gabrielmello32936 жыл бұрын
If you have a million cases of small number of particles, you're gonna want to use the fastest one on small number of particles.
@guilhermegondin1516 жыл бұрын
Just one question, you've said that chan's algorithm is the most efficient one, but in the video The graham's algorithm ends early. Is this because of the diferent distributions or was it intencional? Also, would be nice if you mention the asymptotic analysis, just for a numerical reference of how better one is then another.
@guilhermegondin1516 жыл бұрын
By "was it intencional" I mean, did you chose some special case in with it would do better for some reason?
@LeiosLabs6 жыл бұрын
Yeah, we have 2/3 of these in the algorithm archive: www.algorithm-archive.org/chapters/computational_geometry/gift_wrapping/jarvis_march/jarvis_march.html I am working on getting a better description of these. Basically Chan's is faster because it uses the graham scan where it is useful (large number of points), and it uses the jarvis march where it is useful (small number)
@Abdega6 жыл бұрын
I’m gonna try ordering a Graham Scan at Denny’s
@LeiosLabs6 жыл бұрын
How did that go?
@freeshavaacadooo10956 жыл бұрын
Graham's seems like the most efficient.
@LeiosLabs6 жыл бұрын
Chan's is literally graham's when it's most efficient and jarvis's when it's most efficient. That's why it's *slightly* better.
@andywright88036 жыл бұрын
Why not just start with the leftmost point and a vertical line, then gradually rotate the line about that point clockwise until it intersects with another point, then continue to rotate about the new point until you intersect a new point and continue until you have gone all the way round . You're welcome.
@LeiosLabs6 жыл бұрын
I think the main problem with this implementation is recognizing what intersects with what. I can imagine that would be costly computationally.