In the Art Gallery Problem we are given a polygon P \subset [0,L]^2 on n
vertices and a number k. We want to find a guard set G of size k, such that each point in
P is seen by a guard in G. Formally, a guard g sees a point p \in P if the line segment pg
is fully contained inside the polygon P. The history and practical findings indicate that
irrational coordinates are a "very rare" phenomenon. We give a theoretical explanation.
Next to worst case analysis, Smoothed Analysis gained popularity to explain the practical
performance of algorithms, even if they perform badly in the worst case. The idea is to
study the expected performance on small perturbations of the worst input. The performance
is measured in terms of the magnitude \delta of the perturbation and the input size. We
consider four different models of perturbation. We show that the expected number of bits
to describe optimal guard positions per guard is logarithmic in the input and the
magnitude of the perturbation. This shows from a theoretical perspective that rational
guards with small bit-complexity are typical. Note that describing the guard position is
the bottleneck to show NP-membership. The significance of our results is that algebraic
methods are not needed to solve the Art Gallery Problem in typical instances. This is the
first time an ER-complete problem was analyzed by Smoothed Analysis.
This is joint work with Michael Dobbins and Andreas Holmsen.
May 06, 2019 | 04:00 PM s.t.
Technische Universität Berlin
Institut für Mathematik
Straße des 17. Juni 136
Room MA 041 (Ground Floor)