Algorithms for computing diffuse reflection paths in polygons



Friday, 6 June 2014, 14:30 to 16:00



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.

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)