Hi Prof Kevin, In the Triangulation shown @1:47 I can't find a voronoi edge corresponding to bottom most slanting edge, the points of this edge are also lying in non-neighbouring vornoi cells, Am I missing something here?
excellent question! The reason that you don't see the corresponding edge of the Voronoi diagram is that it is that we only see the part of the Voronoi diagram that fits the slide. If you look at the two Voronoi diagram edges pointing downwards, then you see that they would eventually meet (very far down), and at that point we get a new Voronoi edge that corresponds to the Delaunay edge that you pointed out. Does that clarify the figure?
Before coming to the second lemma, let me first point out that in the first lemma the expected number of created triangles refers to the whole process, i.e., n insertions. If we just look at one insertion, then the expected number of created triangles is
You have explained it in a best possible way. Thanks for such a informative quality video 👍🏻
Very very helpful! Thank you!
Love your content, clears out everything, please continue making these videos
Great to hear! After a long pause, I just uploaded a new geometry video (on convex hulls) 🙂
Informative video. I love it
Great to hear, thanks!
cybertrucks can be defined with just a few points, and cut from a single sheet. Voronoi driving one in heaven right now
Hi Prof Kevin, In the Triangulation shown @1:47 I can't find a voronoi edge corresponding to bottom most slanting edge, the points of this edge are also lying in non-neighbouring vornoi cells, Am I missing something here?
excellent question! The reason that you don't see the corresponding edge of the Voronoi diagram is that it is that we only see the part of the Voronoi diagram that fits the slide. If you look at the two Voronoi diagram edges pointing downwards, then you see that they would eventually meet (very far down), and at that point we get a new Voronoi edge that corresponds to the Delaunay edge that you pointed out. Does that clarify the figure?
Thank you for the reply, So we have to careful enough to consider invisible voronoi edges(if any) as well!
Thanks for such a nice video! On the last page, why the expected time is O(nlogn) instead of O(n^2logn)? Since we need to insert n points.
Before coming to the second lemma, let me first point out that in the first lemma the expected number of created triangles refers to the whole process, i.e., n insertions. If we just look at one insertion, then the expected number of created triangles is
@@algorithmslab I see. Thank you so much!