BEGIN:VCALENDAR
CALSCALE:GREGORIAN
PRODID:iCalendar-Ruby
VERSION:2.0
BEGIN:VEVENT
DESCRIPTION: 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 coor
dinates are a "very rare" phenomenon. We give a theoretical explanation. Ne
xt 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 perturb
ations of the worst input. The performance is measured in terms of the magn
itude \delta of the perturbation and the input size. We consider four diffe
rent models of perturbation. We show that the expected number of bits to de
scribe optimal guard positions per guard is logarithmic in the input and th
e magnitude of the perturbation. This shows from a theoretical perspective
that rational guards with small bit-complexity are typical. Note that descr
ibing the guard position is the bottleneck to show NP-membership. The signi
ficance of our results is that algebraic methods are not needed to solve th
e Art Gallery Problem in typical instances. This is the first time an ER-co
mplete problem was analyzed by Smoothed Analysis. This is joint work with
Michael Dobbins and Andreas Holmsen.
DTSTAMP:20200921T161900
DTSTART:20190506T160000
CLASS:PUBLIC
LOCATION:Technische Universität Berlin\n Institut für Mathematik\n Straße d
es 17. Juni 136\n 10623 Berlin\n Room MA 041 (Ground Floor)
SEQUENCE:0
SUMMARY:Tillmann Miltzow (Universität Utrecht): Smoothed Analysis of the Ar
t Gallery Problem
UID:95690649@www.facetsofcomplexity.de
URL:http://www.facetsofcomplexity.de/monday/20190506-C-Miltzow.html
END:VEVENT
END:VCALENDAR