An Almost Linear Time Algorithm for Field Splitting in Radiation Therapy.
An Almost Linear Time Algorithm for Field Splitting in Radiation Therapy.
复制标题
放射治疗中场分裂的几乎线性时间算法。
DOI：
10.1016/j.comgeo.2012.11.001
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Buatti,JohnM
中科院分区：
文献类型：
--
作者：
Wu,Xiaodong;Dou,Xin;Bayouth,JohnE;Buatti,JohnM
在本文中，我们研究了一个有趣的几何划分问题，称为最佳的字段分裂，这是在调强放射治疗（IMRT）中出现的。在当前的临床实践中，具有最大叶展度约束的多叶准直器（MLC）用于递送规定的强度图（IM）。然而，MLC的最大叶展度可能需要将大的强度图分割成若干重叠的子IM，其中每个子IM被单独递送。我们开发了一个接近线性的时间算法来解决字段分裂问题，同时最大限度地减少所产生的子IM的总复杂性，从而提高治疗效率。同时，我们的算法努力最大限度地减少这些子IM的最大波束开启时间。我们的基本思想是制定字段分裂问题计算最短路径的有向无环图，它表示一个特殊的“分层”结构。图的边权重满足Monge性质，这使我们能够通过只检查图的一小部分来解决这个最短路径问题，从而产生接近线性的时间算法。为了最大限度地减少所产生的子即时通讯的最大光束上的时间，我们考虑一个有趣的最小最大斜率路径问题，在一个单调的多边形，这是可解的线性时间。最小-最大斜率路径问题本身可能是令人感兴趣的。基于真实的医学数据和计算机生成的IM的实验结果表明，我们的新算法运行速度快，产生高质量的字段分裂结果。
In this paper, we study an interesting geometric partition problem, called optimal field splitting, which arises in Intensity-Modulated Radiation Therapy (IMRT). In current clinical practice, a multi-leaf collimator (MLC) with a maximum leaf spread constraint is used to deliver the prescribed intensity maps (IMs). However, the maximum leaf spread of a MLC may require to split a large intensity map into several overlapping sub-IMs with each being delivered separately. We develop a close-to-linear time algorithm for solving the field splitting problem while minimizing the total complexity of the resulting sub-IMs, thus improving the treatment delivery efficiency. Meanwhile, our algorithm strives to minimize the maximum beam-on time of those sub-IMs. Our basic idea is to formulate the field splitting problem as computing a shortest path in a directed acyclic graph, which expresses a special “layered” structure. The edge weights of the graph satisfy the Monge property, which enables us to solve this shortest path problem by examining only a small portion of the graph, yielding a close-to-linear time algorithm. To minimize the maximum beam-on time of the resulting sub-IMs, we consider an interesting min–max slope path problem in a monotone polygon which is solvable in linear time. The min–max slope path problem may be of interest in its own right. Experimental results based on real medical data and computer generated IMs showed that our new algorithm runs fast and produces high quality field splitting results.