Tata Institute of Fundamental Research
Algorithms for computing diffuse reflection paths in polygons
Seminar
Speaker:
Pritam Bhattacharya
Organiser:
Karthyek Rajhaa A M
Date:
Friday, 6 Jun 2014, 14:30 to 16:00
Venue:
D-405 (D-Block Seminar Room)
(Scan to add to calendar)
Abstract:
Let s be a point source of light inside an n-sided polygon P. A polygonal path from s to some point t inside P is called a diffuse reflection path if the turning points of the path lie on edges of P. A diffuse reflection path is said to be optimal if it has the minimum number of reflections on the path. In this talk, I will present three different algorithms for this problem which produce suboptimal paths, but provide some performance guarantees.
For constructing such a path, the first algorithm uses a greedy method, the second algorithm uses a transformation of a minimum link path, and the third algorithm uses the edge-edge visibility graph of P. The first two algorithms work only for polygons without holes, and they run in O( n + k log n ) time, where k denotes the number of reflections in the constructed path. The third algorithm works for polygons with or without holes, and it runs in O(n^2) time. Moreover, the number of reflections in the path produced by this third algorithm is guaranteed to be at most thrice that of an optimal diffuse reflection path.
REFERENCE:
Subir Kumar Ghosh, Partha P. Goswami, Anil Maheshwari, Subhas C. Nandy, Sudebkumar Prasant Pal, Swami Sarvattomananda: Algorithms for computing diffuse reflection paths in polygons. The Visual Computer 28(12): 1229-1237 (2012)
| Speaker: | Pritam Bhattacharya |
| Organiser: | Karthyek Rajhaa A M |
| Date: | Friday, 6 Jun 2014, 14:30 to 16:00 |
| Venue: | D-405 (D-Block Seminar Room) |
(Scan to add to calendar)
Abstract:
Let s be a point source of light inside an n-sided polygon P. A polygonal path from s to some point t inside P is called a diffuse reflection path if the turning points of the path lie on edges of P. A diffuse reflection path is said to be optimal if it has the minimum number of reflections on the path. In this talk, I will present three different algorithms for this problem which produce suboptimal paths, but provide some performance guarantees.
For constructing such a path, the first algorithm uses a greedy method, the second algorithm uses a transformation of a minimum link path, and the third algorithm uses the edge-edge visibility graph of P. The first two algorithms work only for polygons without holes, and they run in O( n + k log n ) time, where k denotes the number of reflections in the constructed path. The third algorithm works for polygons with or without holes, and it runs in O(n^2) time. Moreover, the number of reflections in the path produced by this third algorithm is guaranteed to be at most thrice that of an optimal diffuse reflection path.
REFERENCE:
Subir Kumar Ghosh, Partha P. Goswami, Anil Maheshwari, Subhas C. Nandy, Sudebkumar Prasant Pal, Swami Sarvattomananda: Algorithms for computing diffuse reflection paths in polygons. The Visual Computer 28(12): 1229-1237 (2012)
For constructing such a path, the first algorithm uses a greedy method, the second algorithm uses a transformation of a minimum link path, and the third algorithm uses the edge-edge visibility graph of P. The first two algorithms work only for polygons without holes, and they run in O( n + k log n ) time, where k denotes the number of reflections in the constructed path. The third algorithm works for polygons with or without holes, and it runs in O(n^2) time. Moreover, the number of reflections in the path produced by this third algorithm is guaranteed to be at most thrice that of an optimal diffuse reflection path.
REFERENCE:
Subir Kumar Ghosh, Partha P. Goswami, Anil Maheshwari, Subhas C. Nandy, Sudebkumar Prasant Pal, Swami Sarvattomananda: Algorithms for computing diffuse reflection paths in polygons. The Visual Computer 28(12): 1229-1237 (2012)