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

10623 Berlin

Room MA 041 (Ground Floor)