Solving the Art Gallery Problem |

#mathematics #optimization

0:00 Introduction
1:31 Basics about Polygons
3:53 The Art Gallery Problem
7:42 Triangulating a Simple Polygon
12:52 Chvátal's Art Gallery Theorem
17:30 The Set Cover Problem
26:04 SCP and AGP
31:33 Reference-Paper
32:22 AGP with Witnesses
39:05 Solving AGP using AGPW
44:19 Summary and Applications
48:22 Outro Short-Film

Correction:
5:05 The exact and clean way to check whether the line gp lies inside the polygon would be to check for intersections between the line and the polygon edges (i.e., the consecutive pairs of vertices).

Reference-Paper for Part 2 of the video:
https://dl.acm.org/doi/abs/10.1145/28...
or see here (PDF):
https://cedric.cnam.fr/~bentzc/INITRE...

Animations have been created with Manim and Adobe Premiere Pro.
Manim: https://docs.manim.community/en/stable/

+++ Music courtesy of www.epidemicsound.com +++
▶ Last Snow - Hampus Naeselius
▶ Awaiting Backup - Experia

▶ Vincent Rubinetti
Download the music on Bandcamp:
https://vincerubinetti.bandcamp.com/a...
Stream the music on Spotify:
https://open.spotify.com/playlist/3zN...

Sound effects:
▶ https://www.epidemicsound.com/sound-e...

SVG/PNG graphic files:
▶ Lamp: https://www.vecteezy.com/png/19906450...
▶ Scissor: https://www.vecteezy.com/vector-art/2...
▶ Egg: https://de.pngtree.com/freepng/boiled...
▶ Brokkoli: https://de.pngtree.com/freepng/hand-p...
▶ Sweet Potato: https://de.pngtree.com/freepng/sweet-...
▶ Mushroom: https://de.pngtree.com/freepng/mushro...
▶ Carrot: https://de.pngtree.com/freepng/carrot...
▶ Newton: https://de.pngtree.com/freepng/sir-is...

▶ Fire Animation: https://www.vecteezy.com/video/103661...