Geometric algorithms for static leaf sequencing problems in radiation therapy

ABSTRACT

The static leaf sequencing (SLS) problem arises in radiation therapy for cancer treatments, aiming to accomplish the delivery of a radiation prescription to a target tumor in the minimum amount of delivery time. Geometrically, the SLS problem can be formulated as a 3-D partition problem for which the 2-D problem of partitioning a polygonal domain (possibly with holes) into a minimum set of monotone polygons is a special case. In this paper, we present new geometric algorithms for a basic case of the 3-D SLS problem (which is also of clinical value) and for the general 3-D SLS problem. Our basic 3-D SLS algorithm, based on new geometric observations, produces guaranteed optimal quality solutions using Steiner points in polynomial time; the previously best known basic 3-D SLS algorithm gives optimal outputs only for the case without any Steiner points, and its time bound involves a multiplicative factor of a factorial function of the input. Our general 3-D SLS algorithm is based on our basic 3-D SLS algorithm and a polynomial time algorithm for partitioning a polygonal domain (possibly with holes) into a minimum set of x-monotone polygons, and has a fast running time. Experiments and comparisons using real medical data and on a real radiotherapy machine have shown that our 3-D SLS algorithms and software produce treatment plans that use significantly shorter delivery time and give better treatment quality than the current most popular commercial treatment planning system and the most well-known SLS algorithm. Some of our techniques and geometric procedures (e.g., for the problem of partitioning a polygonal domain into a minimum set of x-monotone polygons) are interesting in their own right.

REFERENCES

• 1: Ravindra K. Ahuja , Thomas L. Magnanti , James B. Orlin, Network flows: theory, algorithms, and applications, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 2: E. M. Arkin , R. Connelly , J. S. Mitchell, On monotone paths among obstacles with applications to planning assemblies, Proceedings of the fifth annual symposium on Computational geometry, p.334-343, June 05-07, 1989, Saarbruchen, West Germany [doi>10.1145/73833.73870]
• 3: T.R. Bortfeld, A.L. Boyer, W. Schlegel, D.L. Kahler, and T.L. Waldron. Experimental verification of multileaf conformal radiotherapy. In A.R. Hounsell, J.M. Wilkinson, and P.C. Williams, editors, Proc. 11th Int. Conf. on the Use of Computers in Radiation Therapy, pages 180--181, 1994.
• 4: T.R. Bortfeld, A.L. Boyer, W. Schlegel, D.L. Kahler, and T.L. Waldron. Realization and verification of three-dimensional conformal radiotherapy with modulated fields. Int. J. Radiat. Oncol. Biol. Phys., 30:899--908, 1994.
• 5: T.R. Bortfeld, D.L. Kahler, T.J. Waldron, and A.L. Boyer. X-ray field compensation with multileaf collimators. Int. J. Radiat. Oncol. Biol. Phys., 28:723--730, 1994.
• 6: T.R. Bortfeld, J. Stein, K. Preiser, and K. Hartwig. Intensity modulation for optimized conformal therapy. In Proc. Symp. Principles and Practice of 3-D Radiation Treatment Planning, 1996.
• 7: A.L. Boyer. Use of MLC for intensity modulation. Med. Phys., 21:1007, 1994.
• 8: A.L. Boyer, T.R. Bortfeld, D.L. Kahler, and T.J. Waldron. MLC modulation of X-ray beams in discrete steps. In Proc. 11th Int. Conf. on the Use of Computers in Radiation Therapy, pages 178--179, 1994.
• 9: A.L. Boyer and C.X. Yu. Delivery of intensity-modulated radiation therapy using dynamic multileaf collimator. In Seminar in Radiat. Oncol., volume 9, 1999.
• 10: M. Carol. An automatic 3-D treatment planning and implementation system for optimized conformal therapy. In 34th Annual Meeting of the American Society for Therapeutic Radiology and Oncology (ASTRO), 1992.
• 11: Wun-Tat Chan , Francis Y. L. Chin, Efficient algorithms for finding the maximum number of disjoint paths in grids, Journal of Algorithms, v.34 n.2, p.337-369, Feb. 2000 [doi>10.1006/jagm.1999.1054]
• 12: Wun-Tat Chan , Francis Y. L. Chin , Hing-Fung Ting, Escaping a grid by edge-disjoint paths, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.726-734, January 09-11, 2000, San Francisco, California, United States
• 13: Danny Z. Chen , Xiaobo Hu , Xiaodong Wu, Maximum Red/Blue Interval Matching with Applications, Proceedings of the 7th Annual International Conference on Computing and Combinatorics, p.150-158, August 20-23, 2001
• 14: Danny Z. Chen , Xiaobo Hu , Shuang Luan , Xiaodong Wu , Cedric X. Yu, Optimal Terrain Construction Problems and Applications in Intensity-Modulated Radiation Therapy, Proceedings of the 10th Annual European Symposium on Algorithms, p.270-283, September 17-21, 2002
• 15: D.J. Convery and S. Webb. Generation of discrete beam-intensity modulation by dynamic multileaf collimation under minimum leaf separation constraints. Phys. Med. Biol., 43:2521--2538, 1998.
• 16: J. Dai and Y. Zhu. Minimizing the number of segments in a delivery sequence for intensity modulated radiation therapy with multileaf collimator. Med. Phys., 28(10):2113--2120, 2001.
• 17: M.N. Du, C.X. Yu, J.W. Wong, M. Symons, D. Yan, R.C. Matter, and A. Martinez. A multi-leaf collimator prescription preparation system for conventional radiotherapy. Int. J. Radiat. Oncol. Biol. Phys., 30(3):707--714, 1994.
• 18: P.M. Evans, V.N. Hansen, and W. Swindell. The optimum intensities for multiple static collimator field compensation. Med. Phys., 24(7):1147--1156, 1997.
• 19: L.R. Ford and D.R. Fulkerson. Maximal flow through a network. Canad. J. Math., 8:399--4045, 1956.
• 20: G. Gademann, W. Schlegel, G. Becker, J. Romahn, K.H. Hover, O. Pastyr, G. van Kaick, and M. Wannenmacher. High precision photon radiotherapy of head and neck tumors by means of an integrated stereotactic and 3D planning system. Int. J. Radiation Oncology Biol. Phys., 19(S1):135, 1990.
• 21: John Hershberger , Subhash Suri, Efficient Breakout Routing in Printed Circuit Boards (Extended Abstract), Proceedings of the 5th International Workshop on Algorithms and Data Structures, p.462-471, August 06-08, 1997
• 22: T.W. Holmes, A.R. Bleier, M.P. Carol, B.H. Curran, A.A. Kania, R.J. Lalonde, L.S. Larson, and E.S. Sternick. The effect of MLC leakage on the calculation and delivery of intensity modulated radiation therapy. In Proc. 12th Int. Conf. on the Use of Computers in Radiation Therapy, pages 346--349, 1997.
• 23: J.E. Hopcroft and R.M. Karp. An n 5/2 algorithm for maximum matching in bipartite graphs. SIAM J. Comput., 2:225--231, 1973.
• 24: J.M. Keil. Decomposing a polygon into simpler components. SIAM J. Comput., 14(4):799--817, 1985.
• 25: J.M. Keil. Polygon decomposition. In J.-R. Sack and J. Urrutia, editors, Handbook on Computational Geometry. Elsevier Science Publishers, 1999.
• 26: H. Kobayashi, S. Sakuma, O. Kaii, and H. Yogo. Computer-assisted conformation radiotherapy with a variable thickness multi-leaf filter. Int. J. Radiation Oncology Biol. Phys., 16(6):1631--1635, 1989.
• 27: D.D. Leavitt, F.A. Gibbs, M.P. Heilbrun, J.H. Moeller, and G.A. Takach. Dynamic field shaping to optimize stereotaxic radiosurgery. Int. J. Radiat. Oncol. Biol. Phys., 21(5):1247--1255, 1991.
• 28: D.D. Leavitt, M. Martin, J.H. Moeller, and W.L. Lee. Dynamic wedge field techniques through computer-controlled collimator or motion and dose delivery. Med. Phys., 17(1):87--91, 1990.
• 29: C. Lee. Personal communication, Department of Radiation Oncology, University of Maryland School of Medicine. October 2002.
• 30: A. Lingas and V. Soltan. Minimum convex partition of a polygon with holes by cuts in given directions. Theory of Computing Systems, 31:507--538, 1998.
• 31: Robin Liu , Simeon Ntafos, On decomposing polygons into uniformly monotone parts, Information Processing Letters, v.27 n.2, p.85-89, February 29, 1988 [doi>10.1016/0020-0190(88)90097-X]
• 32: S. Naqvi. Personal communication, Department of Radiation Oncology, University of Maryland School of Medicine. October 2002.
• 33: L.A. Nedzi, H.M. Kooy, E. Alexander, G.K. Svensson, and J.S. Loeffler. Dynamic field shaping for stereotaxic radiosurgery: A modeling study. Int. J. Radiat. Oncol. Biol. Phys., 25(5):859--869, 1993.
• 34: Leonidas Palios, Connecting the maximum number of nodes in the grid to the boundary with nonintersecting line segments, Journal of Algorithms, v.22 n.1, p.57-92, Jan. 1997 [doi>10.1006/jagm.1995.0798]
• 35: W. Que. Comparison of algorithms for multileaf collimator field segmentation. Med. Phys., 26:2390--2396, 1999.
• 36: Vwani P. Roychowdhury , Jehoshua Bruck, On finding non-intersecting paths in grids and its application in reconfiguring VLSI/WSI arrays, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.454-464, January 22-24, 1990, San Francisco, California, United States
• 37: Achim Schweikard , Rhea Tombropoulos , John Adler, Robotic Radiosurgery with Beams of Adaptable Shapes, Proceedings of the First International Conference on Computer Vision, Virtual Reality and Robotics in Medicine, p.138-149, April 03-06, 1995
• 38: Valeriu Soltan , Alexei Gorpinevich, Minimum dissection of rectilinear polygon with arbitrary holes into rectangles, Proceedings of the eighth annual symposium on Computational geometry, p.296-302, June 10-12, 1992, Berlin, Germany [doi>10.1145/142675.142735]
• 39: S. Webb. The Physics of Conformal Radiotherapy --- Advances in Technology. Bristol, Institute of Physics Publishing, 1997.
• 40: S. Webb. Configuration options for intensity-modulated radiation therapy using multiple static fields shaped by a multileaf collimator. Phys. Med. Biol., 43:241--260, 1998.
• 41: X. Wu, D.Z. Chen, X.S. Hu, S. Luan, L. Zhang, and C.X. Yu. A new leaf-sequencing algorithm for intensity-modulated arc therapy. Medical Physics, 28(6):1252, 2001.
• 42: P. Xia and L.J. Verhey. MLC leaf sequencing algorithm for intensity modulated beams with multiple static segments. Medical Physics, 25:1424--1434, 1998.
• 43: C.X. Yu. Intensity-modulated arc therapy with dynamic multileaf collimation: An alternative to tomotherapy. Phys. Med. Biol., 40:1435--1449, 1995.
• 44: C.X. Yu. Design considerations of the sides of the multileaf collimator. Phys. Med. Biol., 43(5):1335--1342, 1998.
• 45: C.X. Yu. Personal communication, Department of Radiation Oncology, University of Maryland School of Medicine. October 2002.
• 46: C.X. Yu, D. Yan, M.N. Du, S. Zhou, and L.J. Verhey. Optimization of leaf positioning when shaping a radiation field with a multileaf collimator. Phys. Med. Biol., 40(2):305--308, 1995.
• 47: Man-Fai Yu , Wayne Wei-Ming Dai, Single-layer fanout routing and routability analysis for Ball Grid Arrays, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.581-586, November 05-09, 1995, San Jose, California, United States

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

Additional Classification:
  J. Computer Applications
  J.3 LIFE AND MEDICAL SCIENCES

General Terms:
Algorithms, Design, Experimentation, Performance, Theory

Keywords:
IMRT, leaf sequencing, monotone polygons, network flows, polygon partition, radiation therapy