Abstract
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 multileaf collimator (MLC) with a maximum leaf spread constraint is used to deliver the prescribed radiation intensity maps (IMs). However, the maximum leaf spread of an MLC may require to split a large IM into several overlapping sub-IMs with each being delivered separately. We develop an efficient algorithm for solving the field splitting problem while minimizing the total variation of the resulting sub-IMs, thus improving the treatment delivery efficiency. 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 in the graph can be computed by solving an optimal vector decomposition problem using local searching and the proximity scaling technique as we can prove the L\(^\natural\)-convexity and totally unimodularity of the problem. Moreover, 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 time-efficient algorithm.
This research was supported in part by the NSF grants CCF-0830402 and CCF-0844765, and the NIH grant K25-CA123112.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aggarwal, A., Klawe, M., Moran, S., Shor, P., Wilber, R.: Geometric applications of a matrix-searching algorithm. Algorithmica 2(1), 195–208 (1987)
Bortfeld, T., Craft, D., Halabi, T., Trofimov, A., Monz, M., Küfer, K.: Quantifying the Tradeoff Between Complexity and Conformality. Medical Physics 32, 2085 (2005)
Chen, D., Healy, M., Wang, C., Wu, X.: A New Field Splitting Algorithm for Intensity-Modulated Radiation Therapy. In: Lin, G. (ed.) COCOON 2007. LNCS, vol. 4598, p. 4. Springer, Heidelberg (2007)
Chen, D., Hu, X., Luan, S., Wang, C.: Geometric algorithms for static leaf sequencing problems in radiation therapy. In: Proceedings of the nineteenth annual symposium on Computational geometry, pp. 88–97. ACM, New York (2003)
Chen, D., Wang, C.: Field splitting problems in intensity-modulated radiation therapy. In: Asano, T. (ed.) ISAAC 2006. LNCS, vol. 4288, p. 690. Springer, Heidelberg (2006)
Fowler, J., Welsh, J., Howard, S.: Loss of biological effect in prolonged fraction delivery. International journal of radiation oncology, biology, physics 59(1), 242–249 (2004)
Hochbaum, D., Shanthikumar, J.: Convex separable optimization is not much harder than linear optimization. Journal of the ACM (JACM) 37(4), 843–862 (1990)
Kamath, S., Sahni, S., Li, J., Palta, J., Ranka, S.: A Generalized Field Splitting Algorithm for Optimal IMRT Delivery Efficiency. Medical Physics 32, 1890 (2005)
Kamath, S., Sahni, S., Palta, J., Ranka, S.: Algorithms for optimal sequencing of dynamic multileaf collimators. Physics in Medicine and Biology 49(1), 33–54 (2004)
Klawe, M., Kleitman, D.: An almost linear time algorithm for generalized matrix searching. SIAM Journal on Discrete Mathematics 3, 81 (1990)
Kolmogorov, V., Shioura, A.: New Algorithms for the Dual of the Convex Cost Network Flow Problem with Application to Computer Vision. Mathematical Programming (2007) (Submitted)
Murota, K.: Discrete convex analysis. Mathematical Programming 83(1), 313–371 (1998)
Murota, K.: Discrete Convex Analysis: Monographs on Discrete Mathematics and Applications, vol. 10. Society for Industrial and Applied Mathematics, Philadelphia (2003)
Murota, K.: On steepest descent algorithms for discrete convex functions. SIAM Journal on Optimization 14(3), 699–707 (2004)
Oldham, M., Rowbottom, C.: Radiosurgery with a motorized micro-multileaf-collimator: initial experiences in planning and commissioning. In: Proceedings of the 43rd Annual Meeting of the American Association of Physicists in Medicine, AAPM (2001)
Süss, P., Küfer, K.: Smooth intensity maps and the Bortfeld-Boyer sequencer. Berichte des Fraunhofer-Instituts für Techno- und Wirtschaftsmathematik Report 109 (2007)
Webb, S.: Intensity-modulated radiation therapy. Inst. of Physics Pub. Inc. (2001)
Wu, Q., Arnfield, M., Tong, S., Wu, Y., Mohan, R.: Dynamic splitting of large intensity-modulated fields. Physics in Medicine and Biology 45, 1731–1740 (2000)
Wu, X.: Efficient algorithms for intensity map splitting problems in radiation therapy. In: Wang, L. (ed.) COCOON 2005. LNCS, vol. 3595, p. 504. Springer, Heidelberg (2005)
Wu, X., Dou, X., Bayouth, J., Buatti, J.: New algorithm for field splitting in radiation therapy. In: Tokuyama, T. (ed.) ISAAC 2007. LNCS, vol. 4835, pp. 692–703. Springer, Heidelberg (2007)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Liu, Y., Wu, X. (2010). Minimizing Total Variation for Field Splitting with Feathering in Intensity-Modulated Radiation Therapy. In: Lee, DT., Chen, D.Z., Ying, S. (eds) Frontiers in Algorithmics. FAW 2010. Lecture Notes in Computer Science, vol 6213. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-14553-7_9
Download citation
DOI: https://doi.org/10.1007/978-3-642-14553-7_9
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-14552-0
Online ISBN: 978-3-642-14553-7
eBook Packages: Computer ScienceComputer Science (R0)