Solving the Art Gallery Problem | #SoME4

#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/2890491 or see here (PDF): https://cedric.cnam.fr/~bentzc/INITREC/Files/CA4.pdf 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/album/the-music-of-3blue1brown Stream the music on Spotify: https://open.spotify.com/playlist/3zNK20qC96mVSww60lVi1k Sound effects: ▶ https://www.epidemicsound.com/sound-effects/ SVG/PNG graphic files: ▶ Lamp: https://www.vecteezy.com/png/19906450-lamp-png-graphic-clipart-design?autodl_token=29345d94e4b1ab90f4f6af8e23c43140672139a0a2095159d9fa9d03619a739d983f41fad85203c2eb8e0e40d985e0b73a8863c0af002e3cd880b0f848a89e4d ▶ Scissor: https://www.vecteezy.com/vector-art/22812487-scissors-icon-vector-illustration-isolated-on-white-background ▶ Egg: https://de.pngtree.com/freepng/boiled-protein-boiled-egg-food-illustration_4509390.html ▶ Brokkoli: https://de.pngtree.com/freepng/hand-painted-food-vegetables-broccoli_3839425.html ▶ Sweet Potato: https://de.pngtree.com/freepng/sweet-potato-cartoon-image-hand-drawn-material_4678067.html ▶ Mushroom: https://de.pngtree.com/freepng/mushroom-cartoon-cartoon-mushroom-lovely_3921240.html ▶ Carrot: https://de.pngtree.com/freepng/carrot-vector-clipart_7385684.html ▶ Newton: https://de.pngtree.com/freepng/sir-isaac-newton-vintage_15551029.html ▶ Fire Animation: https://www.vecteezy.com/video/10366199-fire-frame-loop-effect-burning-background-with-fire-abstract-background-seamless-loop-fire-burn-flame-energy-4k