Ghosh, Subir Kumar ; Goswami, Partha Pratim ; Maheshwari, Anil ; Nandy, Subhas Chandra ; Pal, Sudebkumar Prasant ; Sarvattomananda, Swami
(2009)
*Algorithms for computing diffuse reflection paths in polygons*
Lecture Notes in Computer Science, 5431
.
pp. 47-58.
ISSN 0302-9743

Full text not available from this repository.

Official URL: http://www.springerlink.com/content/y47k18881l2812...

Related URL: http://dx.doi.org/10.1007/978-3-642-00202-1_5

## Abstract

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 logn) 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(n^{2}) 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.

Item Type: | Article |
---|---|

Source: | Copyright of this article belongs to Springer. |

ID Code: | 76293 |

Deposited On: | 31 Dec 2011 08:58 |

Last Modified: | 31 Dec 2011 08:58 |

Repository Staff Only: item control page