Determining an optimal penetration among weighted regions in two and three dimensions
Danny Z. Chen, Ovidiu Daescu, Xiaobo Sharon Hu, Xiaodong Wu, Jinhui Xu · 1999
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(n2td-l)) 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. IntroductionIn this paper, we study the following geometric optimization problem (called optimal penetration problem): Given a subdivision R with a total of n vertices in 2-D or 3-D space, divided in m regions R..i, i = 1,2,. . ., m, find a ray L such that L