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)
