Polygon Triangulation, Art Gallery Problem
In this video, we will look at an algorithm to triangulate a simple polygon in O(n log n) time. A polygon triangulation is a partition of the polygon into triangles by adding edges between vertices of the polygon.
The algorithm has two parts: firstly a sweepline algorithm for partitioning the polygon into y-monotone subpolygons; secondly, a greedy algorithm to triangulate y-monotone polygons.
As motivation we consider the art gallery problem. The art gallery problem asks what the smallest number of "guards" (i.e. points in the polygon) is such that every point in the polygon can be seen by a guard. In particular, we show in the first half of the video that n/3 guards suffice and are sometimes necessary to guard a simply polygon of complexity n.
You can find the game that we mention here: https://kbuchin.github.io/ruler/art/ Feel free to post in the comments how far you got!
00:00 art gallery problem and triangulations
05:14 existence of triangulations
08:14 number of guards needed
09:40 lower bound
10:52 upper bound
13:28 algorithm: overview
14:56 vertex types
17:59 y-monote = no merge/split vertices
19:45 partitioning into y-monotone pieces: ideas of algorithm
22:54 pseudocode
27:02 algorithm analysis
30:48 triangulating a y-monotone polygon
35:41 summary and discussion
Watch video Polygon Triangulation, Art Gallery Problem online without registration, duration hours minute second in high quality. This video was added by user Algorithms Lab 20 October 2022, don't forget to share it with your friends and acquaintances, it has been viewed on our site 2,758 once and liked it 52 people.