Determining an optimal penetration among weighted regions in two and three dimensions

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