Algorithms for computing diffuse reflection paths in polygons

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:

Related URL:


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(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.

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