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