BEGIN:VCALENDAR
CALSCALE:GREGORIAN
PRODID:iCalendar-Ruby
VERSION:2.0
BEGIN:VEVENT
DESCRIPTION: Given a closed simple polygon P\, we say two points p\,q see e
ach other if the segment pq is fully contained in P. The art gallery proble
m seeks a minimum size set G⊂P of guards that sees P completely. The only k
nown algorithm to solve the art gallery problem exactly is attributed to Sh
arir and uses algebraic methods. As the art gallery problem is ∃R-complete\
, it seems impossible to avoid algebraic methods without additional assumpt
ions. To circumvent this problem\, we introduce the notion of vision sta
bility. In order to describe vision stability\, consider an enhanced guard
that can see "around the corner" by an angle of δ or a diminished guard wh
ose vision is "blocked" by an angle δ by reflex vertices. A polygon P has v
ision stability δ if the optimal number of enhanced guards to guard P is th
e same as the optimal number of diminished guards to guard P. We will argue
that most relevant polygons are vision-stable. We describe a one-shot algo
rithm that computes an optimal guard set for vision-stable polygons using p
olynomial time besides solving one integer program. We implemented an it
erative version of the vision-stable algorithm. Its practical performance i
s slower\, but comparable to other state-of-the-art algorithms. Our iterat
ive algorithm is a variation of the one-shot algorithm. It delays some step
s and only computes them only when deemed necessary. Given a chord c of a p
olygon\, we denote by n(c) the number of vertices visible from c. The chord
-width of a polygon is the maximum n(c) over all possible chords c. The set
of vision-stable polygons admits an FPT algorithm when parametrized by the
chord-width. Furthermore\, the one-shot algorithm runs in FPT time when pa
rameterized by the number of reflex vertices. Joint work by Simon Hengeve
ld &\; Tillmann Miltzow.
DTSTAMP:20200921T162400
DTSTART:20201019T160000
CLASS:PUBLIC
LOCATION:online
SEQUENCE:0
SUMMARY:Tillmann Miltzow (Utrecht University): A practical algorithm with p
erformance guarantees for the art-gallery problem
UID:107734652@www.facetsofcomplexity.de
URL:http://www.facetsofcomplexity.de/monday/20201019-C-1st-week-WS-2020-Mil
tzow.html
END:VEVENT
END:VCALENDAR