[Mittagsseminar TI] Mittagsseminar am FREITAG 8.6.2018, 14:15

[Günter Rote <rote@inf.fu-berlin.de>]

Im Rahmen des Seminars der
Theoretischen Informatik der FU Berlin
spricht morgen am

    FREITAG, 8.6.2018, 14:15 Uhr,
    im *Seminarraum 006*, Institut für Informatik, Takustr. 9, 14195 Berlin

    Pritam Bhattacharya, Indian Institute of Technology (IIT), Kharagpur
    zum Thema:
    Approximation and Inapproximability of Guarding Polygons

Zusammenfassung:
The art gallery problem deals with determining the minimum number of guards (or cameras)
that are sufficient to cover or see every point in the interior of an art gallery,
assuming that the guards have 360° visibility and can see an unbounded distance. An art
gallery can be viewed as a polygon P (with or without holes) having a total of n vertices,
while certain points in P can be specified as guards. Any point z in P is said to be
visible from a guard g if the line segment joining z and g does not intersect the exterior
of P. A polygon P is said to be guarded by a set of chosen guards if every interior point
of P is visible from some guard within the guard set. This problem was first posed by
Victor Klee at a conference in 1973, and in course of time it has become one of the
important problems in computational geometry with extensive applications to surveillance
of buildings like airport terminals, railway stations etc.

Most of the standard variants of the art gallery problem have been known to be NP-hard
(though not NP-complete) since a long time, and very recently, these problems were shown
to be ETR-complete. In 1998, Eidenbenz, Stamm and Widmayer established that the art
gallery problem is APX-hard. They also proved that, especially when dealing with input
polygons containing holes, the approximation ratio of O(log n) obtained by Ghosh in 1986
is in fact tight. In 2015, Bhattacharya, Ghosh and Roy showed that the approximation ratio
lower bound of Ω(log n) holds even for the subclass of polygons with holes that are weakly
visible from an edge. However, for the case of simple polygons without holes, a PTAS has
been proposed very recently by Katz for vertex guarding the subclass of simple polygons
that are weakly visible from an edge.

Ghosh also conjectured in 1986 that a constant-factor approximation algorithm exists for
the art gallery problem when only vertex or edge guards are used and the input is
restricted to only simple polygons without holes. In 2015, Bhattacharya, Ghosh and Roy
settled this conjecture for the special class of simple polygons (without holes) that are
weakly visible from an edge by presenting a 6-approximation algorithm for this problem.
Recently, Bhattacharya, Ghosh and Pal designed constant factor approximation algorithms
for guarding general simple polygons (without holes) using vertex guards. In this talk, we
present the outline of these approximation algorithms and  explain the core ideas behind
how they achieve the constant ratios. (see https://arxiv.org/abs/1712.05492)