Diffused Reflection Paths

Anil Maheshwari

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 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 are for polygons without holes, and they run in O(n + k log n) time, where k denote the number of reflections in the path. The third algorithm is for both polygons with or without holes, and it runs in O(n^2) time. The number of reflections in the path produced by this algorithm can be at most 3 times than 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.

Joint Work with Subir Ghosh, Partha Goswami, Anil Maheshwari, Subhas Chandra Nandy, Sudebkumar Prasant Pal, Swami Sarvattomananda