BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/605
DTSTAMP:20230914T125931Z
SUMMARY:Polygon Guarding With Orientation
DESCRIPTION:Speaker: Pritam Bhattacharya (Indian Institute of Technology\nD
epartment of Computer Science and Engineering\nKharagpur 721302)\n\nAbstra
ct: \nAbstract: The art gallery problem is a classical sensor placement pr
oblem that asks for the minimum number of guards required to see every poi
nt in an environment. The standard formulation does not take into account
self-occlusions caused by a person or an object within the environment. Ob
taining good views of an object from all orientations despite self-occlusi
ons is an important requirement for surveillance and visual inspection app
lications. In this talk\, we will see a version of the art gallery problem
under a constraint\, termed △-guarding\, that ensures that all sides of
any convex object are always visible in spite of self-occlusion.\n\nI wil
l present 3 main results in this talk. First\, I will prove that Omega(√
n) guards are always necessary for △-guarding the interior of a simple p
olygon having n vertices. Second\, I will present a O(log c_{opt}) factor
approximation algorithm for △-guarding polygons with or without holes\,
when the guards are restricted to vertices of the polygon\, where c_{opt}
is the optimal number of guards. Third\, I will introduce the problem of
△-guarding a set of line segments connecting points on the boundary of t
he polygon. This is motivated by applications where an object or person of
interest can only move along certain paths in the polygon. If time permit
s\, I will outline a constant factor approximation algorithm for this prob
lem – one of the few such results for art gallery problems.\n
URL:https://www.tcs.tifr.res.in/web/events/605
DTSTART;TZID=Asia/Kolkata:20150612T140000
DTEND;TZID=Asia/Kolkata:20150612T153000
LOCATION:A-212 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR