Delaunay triangulations (Delaunay triangulations and Voronoi diagrams, part 2)

Рет қаралды 7,577

Күн бұрын

An introduction to Delaunay triangulations, including why they are angle-optimal (in general position) and including a randomized incremental construction with backward analysis
0:00 Delaunay triangulations
1:34 Property: plane graph
4:37 Characterization
9:13 Angle-optimal triangulations
15:41 illegal edges and edge flips
17:25 legal edges and empty circles
22:55 Delaunay = legal (= angle-optimal)
27:58 Randomized incremental construction
28:57 Inserting a point
30:19 LegalizeEdge
30:51 Correctness
32:29 Search Structure
36:58 Analysis
This is the second part of a 2-part series since I typically cover the Voronoi diagram and the Delaunay triangulation in the same lecture. Therefore, this part does not start with a motivation (and rather introduced the Delaunay triangulation as the straight-line dual of Voronoi diagrams).

Пікірлер: 13

@nimishukey 3 жыл бұрын

You have explained it in a best possible way. Thanks for such a informative quality video 👍🏻

@akshitadixit4556 Жыл бұрын

Love your content, clears out everything, please continue making these videos

@algorithmslab Жыл бұрын

Great to hear! After a long pause, I just uploaded a new geometry video (on convex hulls) 🙂

@abyssus9934 2 жыл бұрын

Very very helpful! Thank you!

@micmicmic8325 11 ай бұрын

Informative video. I love it

@algorithmslab 11 ай бұрын

Great to hear, thanks!

@jomsantony2550 2 жыл бұрын

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?

@algorithmslab 2 жыл бұрын

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?

@jomsantony2550 2 жыл бұрын

Thank you for the reply, So we have to careful enough to consider invisible voronoi edges(if any) as well!

@Jason-sq7cc 2 жыл бұрын

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.

@algorithmslab 2 жыл бұрын

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

@Jason-sq7cc 2 жыл бұрын

@@algorithmslab I see. Thank you so much!