Tata Institute of Fundamental Research
Art Gallery Problems for Visibility with Reflection
STCS Student Seminar
Speaker:
Pritam Bhattacharya (Indian Institute of Technology
Department of Computer Science and Engineering
Kharagpur 721302)
Organiser:
Nikhil S Mande
Date:
Friday, 29 May 2015, 14:00 to 15:30
Venue:
A-212 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
Abstract: The art gallery problem is to determine the minimum number of point light sources positioned at vertices of a polygon that can illuminate the entire polygon. Lee and Lin showed that this problem is NP-hard for direct visibility. In this talk, we will show that this problem remains NP-hard even for visibility with reflection, considering both *specular* and *diffuse* reflections. If time permits, I'll also talk about a variant of the art gallery problem known as the kernel problem.
| Speaker: | Pritam Bhattacharya (Indian Institute of Technology Department of Computer Science and Engineering Kharagpur 721302) |
| Organiser: | Nikhil S Mande |
| Date: | Friday, 29 May 2015, 14:00 to 15:30 |
| Venue: | A-212 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
Abstract: The art gallery problem is to determine the minimum number of point light sources positioned at vertices of a polygon that can illuminate the entire polygon. Lee and Lin showed that this problem is NP-hard for direct visibility. In this talk, we will show that this problem remains NP-hard even for visibility with reflection, considering both *specular* and *diffuse* reflections. If time permits, I'll also talk about a variant of the art gallery problem known as the kernel problem.