## Time:

## Venue:

- D-405 (D-Block Seminar Room)

## Organisers:

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)