Algorithms for computing diffuse reflection paths in polygons

摘要

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 edges of P. A diffuse reflection path is said to be optimal if it has the minimum number of reflections on the path. The problem of computing a diffuse reflection path from s to t inside P has not been considered explicitly in the past. We present three different algorithms for this problem which produce suboptimal paths. 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 constructed path. The third algorithm is for polygons with or without holes, and it runs in O(n~2) time. The number of reflections in the path produced by this third algorithm can be at most three times that of an optimal diffuse reflection path. Though the combinatorial approach used in the third algorithm gives a better bound on the number of reflections on the path, the first and the second algorithms stand on the merit of their elegant geometric approaches based on local geometric information.