Determining an optimal penetration among weighted regions in two and threedimensions

We present efficient algorithms for solving the problem of computing an opt imal penetration (a ray or a semi-ray) among weighted regions in 2-D and 3- D spaces. This problem finds applications in several areas, such as radiati on therapy, geological exploration, and environmental engineering. Our algo rithms are based on a combination of geometric techniques and optimization methods. Our geometric analysis shows that the d-D (d = 2, 3) optimal penet ration problem can be reduced to solving O(n(2(d-1))) instances of certain special types of non-linear optimization problems, where n is the total num ber of vertices of the regions. We also give implementation results of our 2-D algorithms.