Speaker: Joe Mitchell
Abstract: A famous problem posed by Victor Klee in the early 1970’s is the Art Gallery Problem: How many points (“guards”) are sufficient to place within a simple polygon P having n vertices so that every point of P is “seen” by at least one guard? This problem falls into a rich class of computational geometry problems that ask one to optimally cover a domain. In recent years, considerable research has been directed at “guarding” problems, from both a mathematical and an algorithmic point of view (no pun intended), since these questions arise in practical problems involving sensor coverage, security cameras, wireless networks, etc. We discuss several interesting mathematical and algorithmic questions that arise in this class, both in the case of stationary guards and mobile robotic guards. The problems are simple to state, easy to visualize, but often very challenging to solve. I will include mention of at least a few open research problems of current interest.