Omrit Filtser (Open University) – Robustly Guarding Polygons

Title: Robustly Guarding Polygons

Abstract: A fundamental set cover problem that arises in geometric domains is the classic Art Gallery Problem: given a geometric domain (e.g., a polygon), place a set of points within the domain, such that every point in it is seen by at least one of the guards. This problem has many variants and has been studied extensively from many perspectives, including combinatorics, complexity, approximation algorithms, and algorithm engineering.
In this talk I will propose precise notions of what it means to robustly guard a domain, under a variety of models. While approximation algorithms for minimizing the number of (precise) point guards in a polygon is a notoriously challenging area of investigation, we show that imposing various degrees of robustness on the notion of visibility coverage leads to a more tractable (and realistic) problem for which we can provide approximation algorithms with constant factor guarantees.

Based on joint work with Rathish Das, Matya Katz, and Joe Mitchell.