Speaker: |
Pritam Bhattacharya (Indian Institute of Technology Department of Computer Science and Engineering Kharagpur 721302) |

Organiser: |
Nikhil S Mande |

Date: |
Friday, 12 Jun 2015, 14:00 to 15:30 |

Venue: |
A-212 (STCS Seminar Room) |

(Scan to add to calendar)

I will 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 polygon 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 the polygon. This is motivated by applications where an object or person of interest can only move along certain paths in the polygon. If time permits, I will outline a constant factor approximation algorithm for this problem – one of the few such results for art gallery problems.