Packing of Unequal Spheres and Automated Radiosurgical Treatment Planning
Packing of Unequal Spheres and Automated Radiosurgical Treatment Planning
复制标题
不等球体的填充和自动放射外科治疗计划
DOI：
10.1023/a:1009831621621
复制
发表时间：
1999
影响因子：
1
通讯作者：
Jie Wang
中科院分区：
文献类型：
--
作者：
Jie Wang
针对放射外科治疗规划问题，研究了将不等长球体包装成三维有界区域的优化问题。给定输入(R，V，S，L)，其中R是3D有界区域，V是正整数，S是球体的多集，L是球体上的位置约束，我们想要使用S中最小数量的球体来找到R的填充，使得覆盖的体积至少是V；满足位置约束L；并且最大化R的边界上被球体接触的点数。这样的包装布置对应于最佳的放射外科治疗计划。然而，找到问题的最佳解决方案在计算上是困难的。特别地，我们证明了该优化问题及相关的几个问题是NP-难的。因此，需要某种形式的近似。一种方法是考虑一个简化的问题，假设任意(整数)直径的球体是无限供应的，并且没有位置限制。这种方法在使用动态规划算法的医学应用中取得了一定的成功(Bourland和Wu，1996；Wu，1996)。本文对该算法提出了一种改进方案，可以大大降低算法的计算量。
We study an optimization problem of packing unequal spheres into a three-dimensional (3D) bounded region in connection with radiosurgical treatment planning. Given an input (R, V, S, L), where R is a 3D bounded region, V a positive integer, S a multiset of spheres, and L a location constraint on spheres, we want to find a packing of R using the minimum number of spheres in S such that the covered volume is at least V; the location constraint L is satisfied; and the number of points on the boundary of R that are touched by spheres is maximized. Such a packing arrangement corresponds to an optimal radiosurgical treatment planning. Finding an optimal solution to the problem, however, is computationally intractable. In particular, we show that this optimization problem and several related problems are NP-hard. Hence, some form of approximations is needed. One approach is to consider a simplified problem under the assumption that spheres of arbitrary (integral) diameters are available with unlimited supply, and there are no location constraints. This approach has met with certain success in medical applications using a dynamic programming algorithm (Bourland and Wu, 1996; Wu, 1996). We propose in this paper an improvement to the algorithm that can greatly reduce its computation cost.