Solving the Art Gallery Problem
Audience: undergraduategraduate
Tags: computational-geometry-graph-theory-polygons-triangulation-set-cover-optimization
The Art Gallery Problem involves determining the smallest number of guards (or 3D cameras) needed to ensure surveillance of an entire art gallery, which is generally represented by a simple polygon. This video will guide you through the basics of simple polygons, their triangulation, important theorems with beautiful proofs, and optimization methods to solve this complex problem.
Analytics
Comments
This is an advanced optimization topic beautifully illustrated and motivated by the art gallery problem.
Amazing Video! Visualization, Voice, Explanation, Everything. Maybe the video is a bit long. Which can be hard to focus on. Good job, keep it going.
Amazing animations and great explanations and easy to follow examples
The graphics are very impressive. I enjoyed the walkthrough of the Triangulation Hypothesis. The pacing is a little slow in places, for example the animation for triangulating the gallery around 12:30 or the DFS animations around 14:20 and 16:30.
Several elements in this video, like the ingredients in the set cover analogy, are too small on a phone.
Captions would have been helpful for parsing some of the less familiar pieces of jargon, such as “weak dual graph”.
Fantastic! I really loved how each part of the video was explained with extremely concrete, visualized examples. The animations were beautiful and engaging. Good job focusing on the interesting parts and not getting bogged down with implementation details. Bravo!
This is a very comprehensive video. I appreciate that the algorithms were both explained in natural language as well as integer linear programming so a computer can understand. However, there were some points where doing so felt repetitive and extended the video. Further, I would be interested in knowing how much this is an improvement over other algorithms. I was told that this reduces the amount of guards, but does this also save on computing time? If so, by how much (would it make sense to consider big O on this NP-hard problem)? Very entertaining video with a fun ending, and a great introduction to set covering and integer linear programming
Really nice animations and pacing. The problem is nicely presented, proofs are explained, etc.
One detail is: when displaying boxes with theorems, corners look really strange. You use light around them which is rounded, but the boxes have sharp corner. I would add a small corner radius, they will look much better.
For animations, take a look at spring animations where movements are not described by Bezier curves with ad hoc shapes, but by actually computing spring physics. Such motions look so much better. I am developing a web app called OrgPad for working with information in form of graphs, and I have written this blog post about how we handle animations and rendering there, you might find some resources there helpful: https://orgpad.info/blog/spanking-browser-for-performance.
Also, as a Czech person, your pronunciation of name “Chvátal” is really bad. You can check the correct reading here: https://translate.google.com/?sl=cs&tl=en&text=Chv%C3%A1tal&op=translate.
Quite a nice interactive video. Reference to Cover of universe set is interesting, but I would appreciate further code brought in to a Github or Notebook of Python. No link to the code in description.