BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/883
DTSTAMP:20230914T125942Z
SUMMARY:Approximation and Inapproximability of Guarding Polygons
DESCRIPTION:Speaker: Pritam Bhattacharya (Indian Institute of Technology\nD
ept. of Computer Science\nand Engineering\nKharagpur\, West Bengal 721302)
\n\nAbstract: \nThe art gallery problem deals with determining the minimum
number of guards (or cameras) that are sufficient to cover or see every p
oint 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 vie
wed 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 s
et of chosen guards if every interior point of P is visible from some guar
d within the guard set. This problem was first posed by Victor Klee at a c
onference in 1973\, and in course of time it has become one of the importa
nt problems in computational geometry with extensive applications to surve
illance of buildings like airport terminals\, railway stations etc.\nMost
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\, t
hese problems were shown to be ETR-complete. In 1998\, Eidenbenz\, Stamm a
nd Widmayer established that the art gallery problem is APX-hard. They als
o proved that\, especially when dealing with input polygons containing hol
es\, the approximation ratio of O(log n) obtained by Ghosh in 1986 is in f
act tight. In 2015\, Bhattacharya\, Ghosh and Roy showed that the approxim
ation ratio lower bound of Ω(log n) holds even for the subclass of polygo
ns 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 weak
ly visible from an edge.\nGhosh also conjectured in 1986 that a constant-f
actor 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 th
is conjecture for the special class of simple polygons (without holes) tha
t are weakly visible from an edge by presenting a 6-approximation algorith
m for this problem. Recently\, Bhattacharya\, Ghosh and Pal designed const
ant 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.\n
URL:https://www.tcs.tifr.res.in/web/events/883
DTSTART;TZID=Asia/Kolkata:20180620T140000
DTEND;TZID=Asia/Kolkata:20180620T150000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR