20090720
Algorithms for computing diffuse reflection paths in polygons
Publication
Publication
Let s be a point source of light inside a polygon P of n vertices. 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 polygonal edges of P. We present three different algorithms for computing diffuse reflection paths from s to t inside P. For constructing such a path, the first algorithm ses a greedy method, the second algorithm uses a transformation of a minimum link path, and the third algorithm uses the edgeedge visibility graph of P. The first two algorithms are for polygons without holes, and they run in O(n + k log n) time, where k denotes the number of reflections in the path. The third algorithm is for both polygons with or without holes, and it runs in O(n2) time. The number of reflections in the path produced by this algorithm can be at most 3 times that of an optimal diffuse reflection path. The problem of computing a diffuse reflection path between two points inside a polygon has not been considered in the past.
Additional Metadata  

dx.doi.org/10.1007/9783642002021_5  
Organisation  School of Computer Science 
Ghosh, S.K. (Subir Kumar), Goswami, P.P. (Partha Pratim), Maheshwari, A, Nandy, S.C. (Subhas Chandra), Pal, S.P. (Sudebkumar Prasant), & Sarvattomananda, S. (Swami). (2009). Algorithms for computing diffuse reflection paths in polygons. doi:10.1007/9783642002021_5
