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
Смотрите видео Polygon Triangulation, Art Gallery Problem онлайн без регистрации, длительностью часов минут секунд в хорошем качестве. Это видео добавил пользователь Algorithms Lab 20 Октябрь 2022, не забудьте поделиться им ссылкой с друзьями и знакомыми, на нашем сайте его посмотрели 2,758 раз и оно понравилось 52 людям.