Single-arc dose painting for precision radiation therapy

Abstract

Provided herein are methods and systems for designing a radiation treatment for a subject using single arc dose painting. The methods and systems comprise an algorithm or a computer-readable product having the same, to plan the radiation treatment. The algorithm converts pairs of multiple leaf collimation (MLC) leaves to sets of leaf aperture sequences that form a shortest path single arc thereof where the pairs of MLC leaves each aligned to an intensity profile of densely-spaced radiation beams, and connects each single arc of leaf apertures to form a final treatment single arc. Also provided is a method for irradiating a tumor in a subject using single arc dose painting.

Claims

1. A method for designing a radiation treatment for a subject using single arc dose painting, comprising: providing an unconstrained optimization map which supplies intensity profiles of densely-spaced radiation beams; aligning each intensity profile to a pair of multiple leaf collimation (MLC) leaves; applying a shortest path algorithm to convert each pair of MLC leaves to a set of leaf aperture sequences, said set of leaf aperture sequences forming a shortest path single arc thereof; .[.and.]. connecting each single arc of leaf apertures to form a final treatment single arc path, thereby designing the single arc dose painting radiation treatment.Iadd.; and delivering a treatment dose of radiation to the subject during a single rotation along one or more of the final treatment single arc path.Iaddend..

2. The method of claim 1, .[.further comprising: delivering.]. .Iadd.wherein the treatment dose is .Iaddend.a continuous dose of radiation .Iadd.delivered .Iaddend.to the subject through each aperture during .[.a.]. .Iadd.the .Iaddend.single rotation .[.along one or more final treatment single arc paths.]..

3. The method of claim 1, further comprising: adjusting a shape of the aperture as a radiation dose delivery angle changes along the final treatment arc.

4. The method of claim 1, wherein the paths of more than one single arc are non-coplanar.

5. The method of claim 1, wherein the apertures sweep back and forth along the single arc path during delivery of the radiation dose.

6. The method of claim 1, wherein sequencing leaf apertures comprises one or more of a line segment approximation on component intensity profiles leaf position, weight optimization of apertures and optimization of leaf position and aperture weight.

7. The method of claim 1, wherein the leaf aperture sequences in each set have one or both of a different starting or ending leaf aperture.

8. The method of claim 7, wherein a starting and ending position of a leaf aperture trajectory are fixed.

9. The method of claim 1, wherein multiple leaf collimation is dynamic.

10. The method of claim 1, further comprising irradiating a tumor in a subject with the continuous dose of radiation through sets of multiple leaf collimation (MLC) aperture sequences during a single rotation along one or more of the treatment single arc paths.

11. The method of claim 10, further comprising: adjusting a shape of the aperture as a radiation dose delivery angle changes along the treatment single arc path.

12. The method of claim 10, further comprising: repeating the irradiation step during another rotation along the treatment single arc path(s).

13. The method of claim 10, wherein each set of MLC aperture sequences form a shortest path single arc thereof, said sets connected to form a shortest path treatment single arc.

14. A system for delivering radiation treatment using single arc dose painting, comprising .Iadd.in a radiation delivery device.Iaddend.: .[.a radiation source for generating a radiation beam;.]. a multiple leaf collimator having a plurality of leafs for shaping .[.the.]. .Iadd.a .Iaddend.radiation beam; structure .[.for generating.]. .Iadd.tangibly storing an algorithm enabling processor-executable instructions to generate .Iaddend.an unconstrained optimization map of intensity profiles of densely-spaced radiation beams; structure .[.for aligning.]. .Iadd.tangibly storing an algorithm enabling processor-executable instructions to align .Iaddend.each intensity profile to a pair of multiple leaf collimation (MLC) leaves; .[.and.]. structure .[.for applying.]. .Iadd.tangibly storing .Iaddend.a shortest path algorithm.[., said shortest path algorithm converting.]. .Iadd.enabling processor-executable instructions to convert .Iaddend.each pair of MLC leaves to a set of leaf aperture sequences forming a shortest path single arc thereof.[., said shortest path algorithm.]. .Iadd.and to .Iaddend.further .[.connecting.]. .Iadd.connect .Iaddend.each single arc of leaf apertures to form a final treatment single arc effective for single arc dose painting.Iadd.; and a source of a dose of continuous radiation beams, varying radiation beams or both deliverable to the subject through each aperture during a single rotation along the final treatment single arc path.Iaddend..

15. The system of claim 14, the shortest path algorithm further .[.adjusting.]. .Iadd.enabling processor-executable instructions to adjust .Iaddend.a shape of the leaf aperture as a radiation dose delivery angle changes along the final treatment single arc.

16. The system of claim 14, wherein the shortest path algorithm .[.sequences.]. .Iadd.enables processor-executable instructions to sequence .Iaddend.leaf apertures via one or more of a line segment approximation on component intensity profiles leaf position, weight optimization of apertures or optimization of leaf position and aperture weight.

17. The system of claim 14, wherein the multiple leaf collimator is dynamic.

.[.18. A computer-readable medium tangibly storing an algorithm to determine a final single arc path for a single arc dose painting radiation treatment, said algorithm enabling processor-executable instructions to: convert pairs of multiple leaf collimation (MLC) leaves to sets of leaf aperture sequences that form a shortest path single arc thereof, said pairs of MLC leaves each aligned to an intensity profile of densely-spaced radiation beams; and connect each single arc of leaf apertures to form a final treatment single arc..].

.[.19. The computer-readable medium of claim 18, said algorithm further enabling instructions to: adjust a shape of the leaf aperture as a radiation dose delivery angle changes along the final treatment single arc..].

.[.20. The computer-readable medium of claim 18, wherein the algorithm sequences leaf apertures via one or more of a line segment approximation on component intensity profiles leaf position, weight optimization of apertures or optimization of leaf position and aperture weight..].

.Iadd.21. A method for designing a radiation treatment using a treatment arc comprising: accessing an optimization map that supplies intensity profiles wherein at least some of the intensity profiles differ from one another with respect to a plurality of radiation beams; aligning specific ones of the intensity profiles to corresponding pairs of multiple leaf collimator (MLC) leaves; determining via a shortest path algorithm, for at least one of the pairs of MLC leaves, a plurality of leaf aperture sequences corresponding to angular intervals as each comprise a part of the treatment arc and combining the plurality of leaf aperture sequences over the angular intervals to form a treatment arc; developing a final treatment arc using the treatment arc; and delivering a dose of radiation to a subject based upon the leaf aperture sequences while traversing the final treatment arc; wherein the dose of radiation comprises a continuous dose of radiation, a varying dose of radiation or both while traversing the final treatment arc..Iaddend.

.Iadd.22. The method of claim 21 wherein the plurality of radiation beams comprises a plurality of densely-spaced radiation beams..Iaddend.

.Iadd.23. The method of claim 22 wherein the plurality of densely-spaced radiation beams are spaced no less than about ten degrees from one another..Iaddend.

.Iadd.24. The method of claim 21, wherein delivering a continuous dose of radiation to the subject comprises, at least in part, sweeping MLC apertures back and forth along the final treatment arc..Iaddend.

.Iadd.25. The method of claim 21 wherein determining a plurality of leaf aperture sequences comprises, at least in part, adjusting MLC aperture shapes as a radiation dose delivery angle changes along the treatment arc..Iaddend.

.Iadd.26. The method of claim 21 wherein determining the plurality of leaf aperture sequences comprises one or more of a line segment approximation on component intensity profiles leaf position, weight optimization of apertures, and optimization of leaf position and aperture weight..Iaddend.

.Iadd.27. The method of claim 21 wherein the plurality of leaf aperture sequences provide for dynamic multiple leaf collimation over the treatment arc..Iaddend.

.Iadd.28. The method of claim 21 wherein the optimization map comprises, at least in part, fluence distribution..Iaddend.

.Iadd.29. A method for designing a radiation treatment comprising: accessing an optimization map that supplies intensity profiles wherein at least some of the intensity profiles differ from one another with respect to a plurality of radiation beams; using the intensity profiles to develop a plurality of multiple leaf collimator aperture settings for use at various angles along a treatment arc; determining via a shortest path algorithm a plurality of leaf aperture sequences from the plurality of multiple leaf collimator aperture settings; using the plurality of leaf aperture sequences to form a radiation treatment plan to deliver a dose of radiation to a subject while dynamically adjusting a corresponding leaf collimator aperture based upon the plurality of leaf aperture sequences while traversing the treatment arc; and delivering a dose of radiation to the subject while traversing the treatment arc using the radiation treatment plan; wherein the dose of radiation comprises a continuous dose of radiation, a varying dose of radiation or both while traversing the treatment arc via the radiation treatment plan..Iaddend.

.Iadd.30. The method of claim 29, wherein delivering the dose of radiation to the subject while dynamically adjusting a corresponding leaf collimator aperture comprises, at least in part, sweeping MLC apertures back and forth along the treatment arc..Iaddend.

.Iadd.31. The method of claim 29 wherein determining a plurality of leaf aperture sequences comprises, at least in part, adjusting MLC aperture shapes as a radiation dose delivery angle changes along the treatment arc..Iaddend.

.Iadd.32. A method for designing a radiation treatment using a treatment arc comprising: accessing an optimization map that supplies intensity profiles wherein at least some of the intensity profiles differ from one another with respect to a plurality of radiation beams; determining via a shortest path algorithm a plurality of multiple leaf collimator aperture sequences corresponding to angular intervals as each comprise a part of the treatment arc and forming the treatment arc based at least in part on the plurality of leaf aperture sequences over the angular intervals to form a treatment arc that provides for sweeping a multiple leaf collimator aperture back and forth along a treatment arc; and delivering a dose of radiation to a subject while sweeping the multiple leaf collimator aperture back and forth along the treatment arc; wherein the dose of radiation comprises a continuous dose of radiation, a varying dose of radiation or both along the treatment arc during delivery..Iaddend.

.Iadd.33. The method of claim 32 wherein the plurality of radiation beams comprises a plurality of densely-spaced radiation beams..Iaddend.

.Iadd.34. The method of claim 33 wherein the plurality of densely-spaced radiation beams are spaced no less than about ten degrees from one another..Iaddend.

.Iadd.35. A planning system for developing a radiation treatment to be administered via a radiation source for generating a plurality of radiation beams and a multiple leaf collimator having a plurality of leafs for shaping the radiation beams, the planning system comprising: structure tangibly storing an algorithm enabling processor-executed instructions to access an optimization map that supplies intensity profiles wherein at least some of the intensity profiles differ from one another with respect to the plurality of radiation beams; structure tangibly storing an algorithm enabling processor-executed instructions to align specific ones of the intensity profiles to corresponding pairs of multiple leaf collimator (MLC) leaves; structure tangibly storing a shortest path algorithm enabling processor-executed instructions to: determine, for at least one of the pairs of MLC leaves, a plurality of leaf aperture sequences corresponding to angular intervals as each comprise a part of the treatment arc; combine the plurality of leaf aperture sequences over the angular intervals to form a treatment arc; and develop a final treatment arc using the treatment arc; a source of a continuous dose of radiation deliverable to a subject based upon the leaf aperture sequences while traversing the single treatment arc; and a source of a varying dose of radiation deliverable to a subject based upon the leaf aperture sequences while traversing the single treatment arc..Iaddend.

.Iadd.36. The planning system of claim 35 wherein the plurality of radiation beams comprises a plurality of densely-spaced radiation beams..Iaddend.

.Iadd.37. The planning system of claim 36 wherein the plurality of densely-spaced radiation beams are spaced no less than about ten degrees from one another..Iaddend.

.Iadd.38. The planning system of claim 35, wherein the source of the continuous dose of radiation is configured to deliver the continuous dose of radiation by, at least in part, sweeping MLC apertures back and forth along the final treatment arc..Iaddend.

.Iadd.39. The planning system of claim 35 wherein the shortest path algorithm enables processor-executed instructions to, at least in part, adjust MLC aperture shapes as a radiation dose delivery angle changes along the treatment arc..Iaddend.

.Iadd.40. The planning system of claim 35 wherein the shortest path algorithm enables processor-executed instructions to use one or more of a line segment approximation on component intensity profiles leaf position, weight optimization of apertures, and optimization of leaf position and aperture weight..Iaddend.

.Iadd.41. The planning system of claim 35 wherein the plurality of leaf aperture sequences provide for dynamic multiple leaf collimation over the treatment arc..Iaddend.

.Iadd.42. The planning system of claim 35 wherein the optimization map comprises, at least in part, fluence distribution..Iaddend.

.Iadd.43. A planning system for developing a radiation treatment to be administered via a radiation source for generating a plurality of radiation beams and a multiple leaf collimator having a plurality of leafs for shaping the radiation beams, the planning system comprising: structure tangibly storing an algorithm enabling processor-executed instructions to access an optimization map that supplies intensity profiles wherein at least some of the intensity profiles differ from one another with respect to a plurality of radiation beams; structure tangibly storing an algorithm enabling processor-executed instructions to use the intensity profiles to develop a plurality of multiple leaf collimator aperture settings for use at various angles along a treatment arc; structure tangibly storing a shortest path algorithm enabling processor-executed instructions to determine a plurality of leaf aperture sequences using the plurality of multiple leaf collimator aperture settings and to use the plurality of leaf aperture sequences to form a radiation treatment plan to deliver a dose of radiation to a subject while dynamically adjusting a corresponding leaf collimator aperture based upon the plurality of leaf aperture sequences while traversing the single treatment arc; and a source of a continuous dose of radiation, a varying dose of radiation or both deliverable to the subject while traversing the single treatment arc..Iaddend.

.Iadd.44. The planning system of claim 43 wherein the shortest path algorithm enables processor-executed instructions to deliver the dose of radiation to the subject by, at least in part, sweeping MLC apertures back and forth along the single treatment arc..Iaddend.

.Iadd.45. The planning system of claim 43 wherein the algorithm for determining a plurality of leaf aperture sequences determines the plurality of leaf aperture sequences by, at least in part, adjusting MLC aperture shapes as a radiation dose delivery angle changes along the treatment arc..Iaddend.

.Iadd.46. A planning system for developing a radiation treatment to be administered via a radiation source for generating a plurality of radiation beams and a multiple leaf collimator having a plurality of leafs for shaping the radiation beams, the planning system comprising: structure tangibly storing an algorithm enabling processor-executed instructions to access an optimization map that supplies intensity profiles wherein at least some of the intensity profiles differ from one another with respect to a plurality of radiation beams; structure tangibly storing a shortest path algorithm enabling processor-executed instructions to: determine a plurality of multiple leaf collimator aperture sequences corresponding to angular intervals as each comprise a part of the treatment arc; and form the treatment arc based at least in part on the plurality of leaf aperture sequences over the angular intervals to form a treatment arc that provides for sweeping a multiple leaf collimator aperture back and forth along the treatment arc; and a source of a continuous dose of radiation, a varying dose of radiation or both deliverable to a subject while sweeping the multiple leaf collimator aperture back and forth along the treatment arc..Iaddend.

.Iadd.47. The planning system of claim 46 wherein the plurality of radiation beams comprises a plurality of densely-spaced radiation beams..Iaddend.

.Iadd.48. The planning system of claim 47 wherein the plurality of densely-spaced radiation beams are spaced no less than about ten degrees from one another..Iaddend.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) FIGS. 1A-1C illustrate how to flip the monotone decreasing path p.sub.r to a monotone increasing path p.sub.r (FIG. 1A), how to flip two monotone decreasing paths p.sub.l and p.sub.r to two monotone increasing paths p.sub.l and p.sub.r (FIG. 1B) and how the xy-monotone region enclosed by the two paths p.sub.l and p.sub.r in FIG. 1B corresponds to a sequence of n vertical bars B.sub.1B.sub.2, . . . , B.sub.n (FIG. 1C). Note that after the flipping operations in FIGS. 1A-1B, neither the steepness nor the closeness constraint is violated, and I.sub.i,pl,pr=I.sub.i,plpr holds for every i, which implies that the total error remains the same.

(2) FIGS. 2A-2D illustrate the transformation of G into ^G (FIGS. 2A-2B) and the layered DAGs G.sub.i1,i1+1, G.sub.i1,i1+2, and G.sub.i1,n (FIG. 2C) where each vertex layer is represented by a vertical line segment, and the set of edges from one vertex layer to the next layer is represented by an arrow and the DAG Gi1 after merging the DAGs G.sub.i1,i1+1, G.sub.i1,i1+2, and G.sub.i1,n (FIG. 2D).

(3) FIGS. 3A-3C illustrate the geometry of the vertex layer L.sub.i of the DAG G for l.sub.start<ir.sub.start, r.sub.start<il.sub.end, and l.sub.end<ir.sub.end. In each figure, all vertices in the vertex layer L.sub.i (or L.sub.i) are mapped to circled points on the 2-D plane; these points form all the lattice points in a convex polygon (possibly degenerated to a line segment) marked by the shaded area.

(4) FIGS. 4A-4B illustrates sliding window leaf sequencing. In FIG. 4A the desired intensity profile is aligned with a leaf pair. FIG. 4B shows separated intensity profiles to be conformed by the leading (right) and training (left) leaves. FIG. 4C shows adjusted leaf traveling trajectories after considering the physical constraints of leaf travel.

(5) FIGS. 5A-5D illustrate steps of the shortest path graph algorithm for converting an intensity profile into k MLC leaf openings with the minimum error.

(6) FIGS. 6A-6C illustrate a step of the shortest path graph algorithm for adjusting a one-dimensional IMAT arc.

(7) FIGS. 7A-7B illustrate the planning of a single arc dose painting.

(8) FIGS. 8A-8B illustrate leaf position and aperture weight optimization using the shortest path graph algorithm.

(9) FIGS. 9A-9D illustrate field width adjustment on the right side (FIGS. 9A-9B) and on the left side (FIGS. 9C-9D).

(10) FIGS. 10A-10C illustrate a planned (FIGS. 10A-10B) and delivered (FIG. 10C) dose distribution for a complicated head and neck case with single arc dose painting.

DETAILED DESCRIPTION OF THE INVENTION

(11) I. Definitions

(12) As used herein the specification, a or an may mean one or more. As used herein in the claim(s), when used in conjunction with the word comprising, the words a or an may mean one or more than one. As used herein another may mean at least a second or more. Furthermore, unless otherwise required by context, singular terms shall include pluralities and plural terms shall include the singular.

(13) As used herein, the term or in the claims is used to mean and/or unless explicitly indicated to refer to alternatives only or the alternatives are mutually exclusive, although the disclosure supports a definition that refers to only alternatives and and/or.

(14) As used herein, about refers to numeric values, including whole numbers, fractions, percentages, etc., whether or not explicitly indicated. The term about generally refers to a range of numerical values, e.g., +/5-10% of the recited value, that one would consider equivalent to the recited value, e.g., having the same function or result. In some instances, the term about may include numerical values that are rounded to the nearest significant figure.

(15) As used herein, the term subject refers to any recipient of single arc dose painting radiation treatment

(16) II. Present Invention

(17) In one embodiment of the present invention there is provided method for designing a radiation treatment for a subject using single arc dose painting, comprising providing an unconstrained optimization map which supplies intensity profiles of densely-spaced radiation beams; aligning each intensity profile to a pair of multiple leaf collimation (MLC) leaves; applying a shortest path algorithm to convert each pair of MLC leaves to a set of leaf aperture sequences, where the set of leaf aperture sequences form a shortest path single arc thereof; and connecting each single arc of leaf apertures to form a final treatment single arc, thereby designing the single arc dose painting radiation treatment.

(18) Further to this embodiment the method comprises delivering a continuous dose of radiation to the subject through each aperture during a single rotation along one or more final treatment single arc paths. In another further embodiment the method comprises adjusting a shape of the aperture as a radiation dose delivery angle changes along the final treatment single arc.

(19) In all embodiments the paths of more than one single arc may be non-coplanar. Also, the apertures may sweep back and forth along the single arc path during delivery of the radiation dose. In addition multiple leaf collimation may be dynamic.

(20) In all embodiments sequencing leaf apertures may comprise one or more of a line segment approximation on component intensity profiles leaf position, weight optimization of apertures or optimization of leaf position and aperture weight. Also, the leaf aperture sequences in each set may have one or both of a different starting or ending leaf aperture. In addition, starting and ending positions of a leaf aperture trajectory may be fixed.

(21) In another further embodiment of the present invention there is provided a method irradiating a tumor in a subject with the continuous dose of radiation through sets of multiple leaf collimation (MLC) aperture sequences during a single rotation along one or more of the treatment single arc paths. Further still to this further embodiment the method may comprise adjusting a shape of the aperture as a radiation dose delivery angle changes along the treatment single arc to keep the dose constant. Further still to both of these further embodiments the method may comprise repeating the irradiation step during another rotation along the treatment single arc path(s).

(22) In another embodiment of the present invention there is provided a system for delivering radiation treatment using single arc dose painting, comprising a radiation source for generating a radiation beam; a multiple leaf collimator having a plurality of leafs for shaping the radiation beam; a structure for generating an unconstrained optimization map of intensity profiles of densely-spaced radiation beams; a structure for aligning each intensity profile to a pair of multiple leaf collimation (MLC) leaves; and a structure for applying a shortest path algorithm, where the shortest path algorithm converts each pair of MLC leaves to a set of leaf aperture sequences forming a shortest path single arc thereof and where the shortest path algorithm further connects each single arc of leaf apertures to form a final treatment single arc effective for single arc dose painting.

(23) Further to this embodiment the shortest path algorithm may adjust a shape of the leaf aperture as a radiation dose delivery angle changes along the final treatment single arc. Also the shortest path algorithm may sequence leaf apertures via one or more of a line segment approximation on component intensity profiles leaf position, weight optimization of apertures or optimization of leaf position and aperture weight. In addition multiple leaf collimation may be dynamic.

(24) In yet another embodiment of the present invention there is provided a computer-readable medium tangibly storing an algorithm to determine a final single arc path for a single arc dose painting radiation treatment, said algorithm enabling processor-executable instructions to convert pairs of multiple leaf collimation (MLC) leaves to sets of leaf aperture sequences that form a shortest path single arc thereof, where the pairs of MLC leaves are each aligned to an intensity profile of densely-spaced radiation beams; and connect each single arc of leaf apertures to form a final treatment single arc. Further to this embodiment the algorithm may enable instructions to adjust a shape of the leaf aperture as a radiation dose delivery angle changes along the final treatment single arc thereby keeping the dose constant. Also, the algorithm may sequence leaf apertures via one or more of a line segment approximation on component intensity profiles leaf position, weight optimization of apertures or optimization of leaf position and aperture weight.

(25) Provided herein are methods and systems to plan and deliver a new rotational radiation therapy, identified herein as single arc dose painting (SADP), that can achieve a quality of treatment comparable to that of multi-arc IMAT using only one continuous rotation of the beam around the patient. The efficiency of such treatment delivery, as compared with that of IMAT, is significantly improved. Generally, the difference in the methods provided herein from prior methods is that the planning process is two steps. In the first step, intensity distributions are optimized over densely spaced beams, for example, on 36 or 72 fields. Because no delivery constraints are applied at the optimization step, the plan quality represents the ultimate. In the second step, the intensity modulated beams are sequenced into a single arc delivery, Planning a single arc capable of delivering the ultimately optimal radiation treatment is based on the recognition that the same intended dose to the tumor delivered by an aperture at a planned angle can be delivered by a slightly modified aperture from a slightly different angle. Consequently, a single rotation with dynamically varying apertures can achieve the same results as a procedure that delivers a plurality of intensity modulated fixed beams.

(26) Furthermore, methods to convert the intensity or fluence patterns in the target, as optimized at fixed beam angles, into a single arc of beam rotation are also new and innovative. The inventive leaf sequencing method of the invention achieves an interconnected relationship of multiple leaf collimator (MLC) apertures so that the MLC leaves are not required to move large distances between adjacent angles of the planned treatment. By sweeping the apertures (windows) back and forth, the requirement of connectedness is much easier to meet.

(27) Also, the dose rate can change among the angular intervals. However, such a change in dose rate is not a requirement. Typically, the aperture size and shape can be optimized to maintain a substantially constant dose rate throughout the entire treatment arc.

(28) Within a planning interval, the apertures can have different weights, delivered either through dose rate variation with all apertures occupying the same angular range or delivered without dose rate variation by allowing the aperture with higher weights to be delivered over a larger angular range. That is, the method is applicable to machines with and without the ability to change dose rates during delivery.

(29) For treatment of tumor or other sites amenable to radiation therapy where use of multiple non-coplanar arcs is beneficial, multiple non-coplanar arcs can be planned according to the methods of the invention. However, with single arc dose painting, it is typically unnecessary to have overlapping arcs. Accordingly, the dose overlap in the tumor is considered, rather than beam overlap in each beam direction as with current IMRT planning. This relies on the recognition that the same dose can be delivered to the tumor by two beam apertures of slightly different shapes directed at the tumor from two angular directions a few degrees apart.

(30) Planning starts with an unconstrained optimization with a large number of beams evenly spaced, for example, every 5-10 degrees. Depending on the complexity of the optimal intensity distribution, different number of apertures and weights are initialized using a sliding window line-segment approximation. Because the initial shapes are derived from the sliding window principle, the apertures are interconnected. The shape and weights of these apertures are further optimized (fine-tuned) to improve the plan quality. To deliver these apertures in one arc, they are spaced within their own planning angular interval by moving the overlapping apertures to other beam angles within the interval. To ensure that the apertures deliver the same dose to the tumor as they are moved away from the planned angle, the aperture shapes are varied, depending on how many degrees they are moved from the planned angle. Adjusting the aperture shape is to faithfully create the intensity maps that were created under unconstrained optimization and to maintain the ultimate plan quality.

(31) Intensity modulation is allowed during intensity optimization and more than one aperture shapes is allowed within each planning angular interval. As compared with IMAT, the apertures are spaced and adjusted within the planning angular interval rather than overlapped to be delivered by using multiple arcs. Because, as described herein, an entire treatment dose is delivered in a single rotation, the number of different apertures per planning angular interval can vary according to the complexity of the required intensity distribution.

(32) As such, systems effective to deliver radiation to a tumor using single arc dose painting comprise those radiation delivery devices having suitable structures for radiation therapy of malignant tumors or other conditions responsive to such treatment. As is known in the art such devices comprise at least a source of radiation, amoveable, rotatable gantry, a multiple leaf collimator, e.g., a dynamic multiple leaf collimater, a platform for a subject receiving radiation therapy, and the necessary computer hardware and software, processor, memory and network or other connections necessary to run the device. In addition, the system comprises a module or structure, such as, but not limited to, a computer memory, a computer-readable memory or computer program to, storage device which is suitable to tangibly store and execute the algorithms described herein, such as, standard algorithms for intensity profile optimization and the novel short path algorithms provided herein.

(33) The following examples are given for the purpose of illustrating various embodiments of the invention and are not meant to limit the present invention in any fashion.

EXAMPLE 1

(34) Constrained Coupled Path Planning (CCPP)

(35) In constrained coupled path planning, the starting and ending points of the sought paths are prespecified. Precisely, the constrained coupled path planning (CCPP) problem is: Given an nH uniform grid R.sub.g, a non-negative function defined on the integers in {1, 2, . . . , n}, and positive integers l.sub.start, r.sub.start, l.sub.end, r.sub.end, c, and (H), find two noncrossing paths p.sub.l and p.sub.r of height H along the edges of R.sub.g to minimize the total error (p.sub.l, p.sub.r) =.sup.n.sub.i+1|l.sub.i,pl,prf(i)|, subject to the following constraints: (1) p.sub.l (resp., pr) starts at (l.sub.start, 0) (resp., (r.sub.start, 0)) and ends at (l.sub.end, H) (resp., (r.sub.end,H)), (2) (the steepness constraint) both p.sub.l and p.sub.r are c-steep paths, and (3) (the closeness constraint) |l.sub.i,pl,prf(i)| for all i=1, 2, . . . , n.

(36) Without loss of generality, it is assumed that l.sub.startl.sub.end and r.sub.startr.sub.end, so that the two sought paths p.sub.l and p.sub.r are both xy-monotone increasing paths. Otherwise, the CCPP problem can be transformed to a new CCPP problem that satisfies this condition. By flipping (FIGS. 1A-1B) one or both of the optimal paths for this new problem, two optimal paths are obtained for the original CCPP problem.

(37) Algorithm for the Case where l.sub.endr.sub.start

(38) It is to be noted that the algorithm can be adapted easily to handle the other case in which l.sub.end<r.sub.start. The region P(p.sub.l, p.sub.r) is a rectilinear xy-monotone polygon in R.sub.g and consists of a sequence of n vertical bars. Thus, the CCPP problem can be solved by transforming it to computing a shortest path in a directed acyclic graph, DAG G. The DAG G (FIG. 2A-2D) also contains a source s, a sink t, and n layers of vertices, L.sub.1, L.sub.2 . . . , L.sub.n, which are defined as follows to satisfy the additional geometric constraints of the CCPP problem:

(39) $\begin{array}{cc}{L}_i^{}\{\begin{array}{cc}\left\{{\left(\left[,\right]\right)}^{\left(i\right)}.Math.==0\mathrm{and}.Math.--f\left(i\right).Math.<\right\}& \mathrm{if}1<=i<=I_{\mathrm{start}}\\ \left\{{\left(\left[,\right]\right)}^{\left(i\right)}.Math.0=<<=H-c\mathrm{and}.Math.--f\left(i\right).Math.<\right\}& \mathrm{if}{I}_{\mathrm{start}}<i<=r_{\mathrm{start}}\\ \left\{{\left(\left[,\right]\right)}^{\left(i\right)}.Math.c<=<=<=H-c\mathrm{and}.Math.--f\left(i\right).Math.<\right\}& \mathrm{if}{r}_{\mathrm{start}}<i<=I_{\mathrm{endt}}\\ \left\{{\left(\left[,\right]\right)}^{\left(i\right)}.Math.c<=<=H\mathrm{and}.Math.--f\left(i\right).Math.<\right\}& \mathrm{if}{I}_{\mathrm{end}}<i<=r_{\mathrm{end}}\\ \left\{{\left(\left[,\right]\right)}^{\left(i\right)}.Math.==H\mathrm{and}.Math.--f\left(i\right).Math.<\right\}& \mathrm{if}{r}_{\mathrm{end}}<i<=n\end{array}& \mathrm{Eq}.\left(1\right)\end{array}$

(40) The weight of a [, ].sup.(i) is defined as ([, ].sup.(i))=f (i)| and the edges of G are defined based on the same domination relation D(,). A shortest s-to-t path in G corresponds to an optimal solution for the CCPP problem and, further, the vertices and edges of G0 have geometric properties similar to those of dominated sets (FIGS. 3A-3C). Such similar dominated sets may be D(H,H), D(,H) (0<<H), D(0,H), D(,) (0<<H) D(0,) (0<<H), and D(0, 0). Thus the shortest path computation can be sped up and the CCPP algorithm takes O(nH) time.

EXAMPLE 2

(41) Computing the Complete Set of all CCPP Problem Instances

(42) Overview of the Algorithm

(43) Given f, n, H, , and c, CCPP problem instances are solved on f, n, H, , c, l.sub.start, r.sub.start, l.sub.end, and r.sub.end for all possible combinations of l.sub.start, r.sub.start, l.sub.end, and r.sub.end. Without loss of generality, only those combinations which satisfy l.sub.startl.sub.end and r.sub.startr.sub.end are considered. All problem instances are classified into two subsets S.sub.1 and S.sub.2, with S.sub.1 (resp., S.sub.2) containing those with l.sub.endr.sub.start (resp., l.sub.end<r.sub.start).

(44) Solving all CCPP Instances in S.sub.1

(45) It is to be noted that this approach can be adapted easily to solve all instances in S.sub.2. Since 0l.sub.startr.sub.startl.sub.endr.sub.endn, there are totally N=(n.sup.4) problem instances, denoted by l.sub.1, l.sub.2, . . . , l.sub.N. Let l.sup.(k).sub.start, r.sup.(k).sub.start, l.sup.(k).sub.end, and r.sup.(k).sub.end be the corresponding specification for the problem instance lk. An instance l.sub.k (1kN) corresponds to a shortest path problem on a vertex-weighted DAG, denoted by G.sub.k, of O(nH) vertices and O(nH.sup.2.sup.2) edges. The key observation is that G.sub.k can be transformed into an edge-weighted DAG, denoted by ^G.sub.k, with only O() vertices and O(.sup.2) edges.

(46) The algorithm consists of two main steps. First, prepare the weights of all edges in ^G.sub.1, ^G.sub.2, . . . , and ^G.sub.N (O(.sup.2) edges for each ^G.sub.k). The weights of all the O(n.sup.4.sup.2) edges are implicitly computed and stored in a batch fashion, in totally O(n.sup.2H.sup.2) time, such that for any edge, its weight can be reported in O(1) time. Second, a shortest path is computed in ^G.sub.1, ^G.sub.2, . . . , and ^G.sub.N, respectively. It is shown that each ^G.sub.k (1kN) is a DAG satisfying the Monge property (1-2,4). Since the weight of any edge can be obtained in O(1) time, a shortest path in ^G.sub.k takes only O() time to compute. The algorithm thus takes O(n.sup.2H.sup.2+n.sup.4) time, improving the straightforward O(n.sup.5H) time algorithm, i.e., applying the CCPP algorithm N=O(n.sup.4) times) by a factor of min{nH, n.sup.3/}.

(47) The Graph Transformation

(48) For fixed l.sub.start, l.sub.end, r.sub.start, and r.sub.end (0l.sub.startr.sub.start l.sub.endr.sub.endn), let l be the corresponding CCPP problem instance and G=(V(G),E(G)) be the vertex-weighted DAG defined in Example 1 for solving l. For u is an element of V(G), denote its weight by (u). For a path p in G, the weight (p) of p is defined as (p)=.sub.u is element of p (u). For u, v is an element of V(G), denote by (u, v) a shortest u-to-v path in G.

(49) An edge-weighted directed graph ^G=(V(^G),E(^G)) is constructed from G as follows (FIGS. 2A-2B). The vertex set V(^G) is a subset of V(^G), and consists of two dummy vertices s and t and four vertex layers:

(50) ${\hat{L}}_1\stackrel{}{=}{L}_{i_{\mathrm{start}}}^{},{\hat{L}}_2\stackrel{}{=}{L}_{r_{\mathrm{start}}}^{},{\hat{L}}_3\stackrel{}{=}{L}_{I_{\mathrm{end}}+1}^{},\mathrm{and}{\hat{L}}_4\stackrel{}{=}{L}_{r_{\mathrm{end}}+1}^{}.$
The edge set E(^G) is simply
U.sub.t1.sup.3({circumflex over (L)}.sub.t{circumflex over (L)}.sub.t+1)({s}{circumflex over (L)}.sub.1)({circumflex over (L)}.sub.4{t}).
Thus, the subgraph of ^G between any two consecutive vertex layers is a complete bipartite graph. For each edge (u, v) is an element of E(^G), a weight ^(u, v)=((u, v)) (u) is assigned to it, i.e., the weight of a shortest u-to-v path in G minus the vertex weight of u. For convenience, ^(u, v).sup.=+ if there is no path from u to v in G.

(51) ^G is an edge-weighted DAG and has O() vertices and O(.sup.2) edges (by the definition of L.sub.i in Example 1). Define the weight ^(p) of a path p in ^G as ^(p)=.sub.e is an element of p ^(e). A shortest s-to-t path in G is closely related to a shortest s-to-t path in ^G. In fact, it is not difficult to show that if p=s.fwdarw.u.sub.1.fwdarw.u.sub.2.fwdarw. . . . .fwdarw.u.sub.n.fwdarw.t is a shortest s-to-t path in G, then ^p=s.fwdarw.u.sub.lstart.fwdarw.u.sub.rstart.fwdarw.U.sub.lend+1.fwdarw.U.sub.rend+1.fwdarw.t is a shortest s-to-t path in ^G, with ^(^p)=(p) This is due to the optimal-substructure property of shortest paths, i.e., any subpath of a shortest path is also a shortest path. Moreover, if s.fwdarw.v.sub.2.fwdarw.v.sub.3.fwdarw.v.sub.4.fwdarw.t is a shortest s-to-t path in ^G, then s v.sub.1 v.sub.2 v.sub.3 v.sub.4

(52) is a shortest s-to-t path in G.

(53) Before explaining why the vertex layers L.sub.lstart, L.sub.rstart, L.sub.lend+1, and L.sub.rend+1, from G for the construction of ^G were chosen, Equation (1) must be reviewed. Observe that if i is fixed and l.sub.start, r.sub.start, lend, and r.sub.end are temporarily viewed as parameters, then Equation (1) implies that the i-th vertex layer in any G (1kN) is in exactly one of five possible states, denoted by .sub.i.sup.(I), .sub.i.sup.(II), .sub.i.sup.(III), .sub.i.sup.(IV), and .sub.i.sup.(V), e.g., .sub.i.sup.(I) if 1il.sub.start). For a fixed k (1kN), in the DAG G.sub.k, the i-th vertex layer L is of type I if L=.sub.i.sup.(I). The type II, III, IV, and V vertex layers are defined similarly.

(54) Clearly, in the DAG G, all vertex layers between s and L.sub.lstart, L.sub.lstart and L.sub.rstart, L.sub.rstart and L.sub.lend+1, L.sub.lend+1, and L.sub.rend+1, and L.sub.rend+1 and t are of type I, II, III, IV, and V, respectively (FIG. 2A). This implies an interesting property: For any edge (u, v) of ^G, all vertex layers between u and v in G are of the same type. As will be shown, this property plays a key role in speeding up the computation of the weights of all edges in the transformed DAGs ^G.sub.1, ^G.sub.2, . . . ^G.sub.N. It should be pointed out that for one DAG G, although ^G is of a much smaller size than G, the weights of the edges of ^G are costly to compute. Thus transforming G to ^G will not yield a faster algorithm for solving a single CCPP problem instance.

(55) Computing the Edge Weights for all Transformed DAGs

(56) It is demonstrated herein how to compute the weights of all edges in the transformed DAGs ^G.sub.1, ^G.sub.2, . . . , ^G.sub.N. Recall that the weight of an edge in ^G.sub.k corresponds to a one-pair shortest path problem instance on G.sub.k. Since every ^G.sub.k has O(.sup.2) edges, there are in total O(n.sup.4.sup.2) edges in ^G.sub.1, ^G.sub.2, . . . , ^G.sub.N, corresponding to O(n.sup.4.sup.2) one-pair shortest path problem instances.

(57) It is stated that the O(n.sup.4.sup.2) edges actually correspond to only O(n.sup.2.sup.2) distinct one-pair shortest path problem instances. For any k that is an element of {1, 2, . . . , N} and for any edge (u, v) that is an element of ^G.sub.k, denote by SP(u, v, k) the corresponding one-pair shortest path instance, i.e., finding a shortest u-to-v path in G.sub.k. Considering the indices of the vertex layers in which u and v lie in ^G.sub.k respectively, there are five cases. Only the most typical case, in which u (resp., v) lies in the 2nd (resp., 3rd) layer of ^G.sub.k is discussed. For this case, let i.sub.1=r.sup.(k).sub.start and i.sub.2=l.sup.(k).sub.end+1; then u is an element of .sup.II.sub.i1V(G.sub.k), v is an element of .sup.IV.sub.i2V(G.sub.k), and all vertex layers between u and v in G.sub.k are of type III (FIG. 2A). Let G.sub.i1,i2 be a layered DAG whose vertices consist of the vertex layers .sup.II.sub.i1, .sup.III.sub.i1+1, .sup.III.sub.i1+2, . . . , .sup.III.sub.i21, and .sup.IV.sub.i2, in this order, and whose edges are defined based on the same domination relation D(,).

(58) Clearly, SP(u, v, k) is equivalent to finding a shortest u-to-v path in G.sub.i1,i2. Since i.sub.i (resp., i2) ranges from 1 to n, G.sub.i1,i2 has O(n.sup.2) possible choices. Note that u (resp., v) belongs to the layer .sup.II.sub.i1 (resp., .sup.IV.sub.i2), which contains O() vertices for any i.sub.i (resp., i.sub.2). It follows that SP(u, v, k) has O(n.sup.4.sup.2) possible choices for the case where u (resp., v) lies in the 2nd (resp., 3rd) layer of ^G.sub.k. Other cases can be analyzed similarly. Since there are five cases, SP(u, v, k) has O(n.sup.2.sup.2)O(1)=O(n.sup.2.sup.2) possible choices in total.

(59) Since there are only O(n.sup.2.sup.2) distinct one-pair shortest path problem instances, it is preferred to implicitly compute and store the weight of each edge of ^G.sub.1, ^G.sub.2, . . . , ^G.sub.N. More specifically, distinct one-pair shortest path instances are solved and the corresponding shortest paths along with their lengths are stored, so that given an edge (u, v) of any ^G.sub.k, its weight can be reported in O(1) time.

(60) It is demonstrated how to solve the O(n.sup.2.sup.2) distinct one-pair shortest path problem instances in a batch fashion. First a set of one-pair shortest path instances are combined into one single-source shortest path problem instance. Second, a set of single-source shortest path instances are solved in one shot by merging the underlying DAGs into one DAG of a comparable size. This approach is illustrated by showing how to solve the one-pair shortest path instances in G.sub.i1,i2 (as defined in the previous paragraph) for all i.sub.1, i.sub.2. Each instance is specified by a source vertex u is an element of .sup.II.sub.i1 and a destination vertex v is an element of .sup.IV.sub.i2. Recall that G.sub.i1,i2 contains the vertex layers .sup.II.sub.i1, .sup.III.sub.i1+1, .sup.III.sub.i1+, . . . , .sup.III.sub.i21, and .sup.IV.sub.i2, For a fixed i.sub.1, the layered DAGs G.sub.i1,i2, for all i.sub.2=i.sub.1+1, . . . , n, can be merged into one DAG, simply denoted by G.sub.i1 (FIGS. 5C-5D). For any vertex u is an element of .sup.II.sub.i1, its single-source shortest paths can be computed in G.sub.i1, in O(nH) time as in the CCPP algorithm. Since |.sup.II.sub.i1|=O() and i.sub.1 ranges from 1 to n, the one-pair shortest path instances in G.sub.i1,i2 can be solved for all i.sub.1, i.sub.2, in O(nH)O(n)O()=O(n.sup.2.sup.2) time.

(61) Shortest Path Computation on the Transformed DAGs

(62) The algorithm for computing a shortest path in the DAG ^G as defined as defined above is presented. The key idea is to show that ^G satisfies the Monge property [1, 2, 4], and thus a shortest path in ^G can be computed by examining only a small portion of its edges.

(63) Consider the vertex layers ^L.sub.2 and ^L.sub.3 of ^G. Clearly, ^L.sub.2=L.sub.rstart={[, ].sup.(rstart)0=<<=Hc and |f (rstart)|}={[0, ].sup.(rstart)|0<<=Hc and |f(rstart)|}). Thus ^L.sub.2 can be written as ^L.sub.2={u.sub.1, u.sub.2, . . . , u.sub.|^L2|}, where u.sub.k=[0, .sub.k].sup.(rstart)(1k|^L.sub.2|) and 0<.sub.1<2< . . . <.sub.|^L2|Hc. Similarly, write ^L.sub.3 as ^L.sub.3={v.sub.1, v.sub.2, . . . , v.sub.|L3|}, where v.sub.k=[.sub.k, H].sup.(lend+1)(1k|^L.sub.3|) and c.sub.1<.sub.2< . . . <.sub.|^L3|<H. The following lemma shows the properties of the edges from the vertices on ^L.sub.2 to ^L.sub.3 in ^G.

(64) Lemma: (A) Let u.sub.i (resp., v.sub.j) be a vertex on ^L.sub.2 (resp., ^L.sub.3) of ^G, with 1i|^L.sub.2| (resp., 1j|^L.sub.3|). If ^(u.sub.i, v.sub.j)=1, then for any j<j (resp., i>i), ^(u.sub.i, v.sub.j)=(resp., ^ (u.sub.i, v.sub.j)=). (B) Let u.sub.i, u.sub.j (resp., v.sub.j, v.sub.j) be two vertices on ^L.sub.2 (resp., ^L.sub.3) of ^G, with 1i<i|^L.sub.2| (resp., 1j<j|^L.sub.3|). If both edges e.sub.1=(u.sub.i, v.sub.j) and e.sub.2=(u.sub.i,v.sub.j) have finite weights, then edges e.sub.3=(u.sub.i, v.sub.j) and e.sub.4=(u.sub.i, v.sub.j) also both have finite weights. Moreover, ^(e.sub.3)+^(e.sub.4) ^(e.sub.1)+^(e.sub.2).

(65) The lemma implies that the matrix A of size |^L.sub.2||^L.sub.3|, with =^(u.sub.i, v.sub.j), is a Monge matrix. Note that for any i and j, ^(u.sub.i, v.sub.j) can be reported in O(1) time as described above. Thus in ^G, once the shortest paths from s to all vertices in ^L.sub.2 are computed, using the Monge matrix multiplication algorithms [1, 2, 4], the shortest paths from s to all vertices in ^L.sub.3 can be computed in O() time. Observe that outside the subgraph of ^G between the vertex layers ^L.sub.2 and ^L.sub.3 (FIG. 2B), there are only O() edges of ^G. Hence a shortest s-to-t path in ^G can be computed in O() time. Thus, the following theorem is:

(66) Given a non-negative function defined on {1, 2, . . . , n} and positive integers c, H, and (H), the complete set of the CCPP problem instances is computable in O(n.sup.2H.sup.2+n4) time.

EXAMPLE 3

(67) Unconstrained Intensity Optimization in Single-arc Dose Painting

(68) The first planning step for single arc dose painting is unconstrained intensity optimization. Different algorithms can be used for achieving this step (11-13). Suitable algorithms are available in the relevant literature (8,10). As with IMAT, an arc is approximated with multiple fixed radiation beams evenly spaced every 5-10 degrees (5).

EXAMPLE 4

(69) Leaf-sequencing in Single-arc Dose Painting

(70) Step two in single-arc dose painting is the conversion of the optimized beam intensities into connected field apertures. The goal is to find a set of connected field shapes that when delivered dynamically based on linear interpolation between the apertures, will result in minimum discrepancy to the optimized intensity profile. For leaf sequencing, a hybrid approach has been developed. For simple cases the method called line segment approximation on component intensity profiles is appropriate. For more complicated cases, leaf position and aperture weight optimization and leaf position and aperture weight optimization may be used.

(71) Line Segment Approximation to Component Intensity Profiles

(72) This method is based on a sliding window technique. Recognizing that any intensity pattern can be delivered by sliding a varying aperture in either direction, each of the intensity patterns can be converted into sliding window dynamic control points. The only constraint to ensure the interconnectedness of the intensity patterns is that in the next interval, the direction of the sliding window has to be in the opposite direction. Accordingly, the apertures defined by the multi-leaf collimator (MLC) sweep back and forth, completing one cycle in every two intervals.

(73) The conversion from fluence distributions to MLC sliding window delivery is illustrated by FIGS. 4A-4B. For a given arbitrary intensity distribution aligned with a pair of opposing leaves, such as that shown in FIG. 4A, initially, a separation is made between the portion to be delivered by the leading leaf (right leaf) and that to be delivered by the trailing leaf (left leaf). With the radiation source turned on, for a fixed left leaf position, moving the right leaf towards the right will create a negative gradient. Likewise, for a fixed right leaf position, moving the left leaf towards the right will create a positive intensity gradient. Therefore, the method first finds the points that separate the positive and negative gradients, as illustrated by the vertical lines. Then positive gradient portions are to the trailing profile and inverted negative gradient portions to the leading profile as shown on FIG. 4B. The vertical axis represents beam intensity in radiation monitor units (MUs), which is also time for a given machine dose rate. With this separation, the profile may be defined as follows:
Original profile=Trailing ProfileLeading profile.
The separated profiles become the leading and trailing leaf positions as functions of time. If both leaves are moved according to FIG. 1B, the desired intensity profile will be created.

(74) Inspection of FIG. 4B, reveals that for both leaves, there will be sections where the leaves are required to change positions with no elapsed time (the flat portions of the profiles). Accordingly, in order to make the dose delivery physically achievable, the minimum gradient required for leaf travel (governed by the maximum leaf traveling speed) is added to the flat portions, while the same amount is added to the other profile so that the difference between the two profiles is kept substantially constant (FIG. 4C). When this intensity profile is delivered, the apertures of varying width formed by both leaves will move smoothly from the left to the right. Such smooth motion is the origin of the term sliding window technique. The left leaf can alternatively be considered to be the leading leaf and the right leaf to be the trailing leaf, thereby delivering the same intensity distribution by sliding the window from the right to the left.

(75) With the current art of dynamic MLC leaf sequencing, the control-points are generated by evenly dividing the total monitor units (MUs) required by the number of segments, which is normally relatively large (50). Rather than a pure sliding window leaf-sequencing as described in FIGS. 4A-4B, it is also possible to sequence the optimized intensity maps in a sliding window fashion using a graph algorithm known and standard in the art. Because the treatment apparatus, linac and MLC, performs the linear interpolation automatically, accurate delivery is ensured if the vertices that join two lines of different slopes are used as control points. Therefore, the gradient turning positions of the original intensity profile (the intercepts of the vertical lines with the profiles) are used as the initial estimations of the control points. In essence, the original component intensity profiles are approximated with connected line segments. These initial control points are used as the input to the next step of the leaf sequencing process.

(76) As indicated in FIGS. 4A-4B, the apertures selected from the sliding window leaf sequence are naturally interconnected within each planning interval. The apertures within each interval will move either left to right or right to left. To make it easier to connect all intervals into one arc, the apertures are sequenced in such a way that: 1) the MLC leaves move in opposite directions in any two neighboring angular intervals; and 2) the two aperture shapes connecting any two angular intervals do not violate the physical constraints of the MLC (i.e., the shapes are not so drastically different as to require large MLC movements). Because any intensity map can be delivered dynamically in either left-to-right or right-to-left leaf motion, the direction of MLC motion alternates between neighboring beams and the aperture shape connectivity is considered throughout the arc. As a result, the shape-varying beam aperture (or dynamic window) slides back and forth while the gantry rotates around the patient.

(77) Leaf Position and Aperture Weight Optimization

(78) One of the concerns presented by method using line segment approximation to component intensity profiles is that for complex intensity distributions, using this method alone may result in a plan with very high machine beam-on times and may requires too many control points to maintain a very close dose conformity. Thus for more complicated cases, two alternative, and somewhat more complex, methods can be used, as described below.

(79) Observe that during the delivery of a set of densely-spaced intensity patterns, each pair of MLC leaves will deliver a set of densely-spaced intensity profiles that are aligned with this leaf pair. The method comprises the following key steps:

(80) First, for every pair of MLC leaves, each of its aligned intensity profiles is converted into a set of k leaf openings using a geometric k-link shortest path algorithm with equal beam-on times that incurs the minimum error. Second, the leaf openings for the same pair of MLC leaves are connected together to form a single-arc of leaf openings using a geometric shortest path algorithm that ensures a smooth transition between adjacent leaf openings while minimizing the error incurred. Third, the single-arcs for each pair of MLC leaves are then combined to form the final single-arc treatment plan.

(81) FIGS. 5A-5D illustrate the key idea of this step. In FIG. 5A, the optimized fluence profile is represented by the functional curve (x) and the resulting simplified profile is the rectilinear functional curve g(x) that is deliverable by k=4 leaf openings with equal beam-on. The error here is the integral of the absolute difference between the two functions, |(x)g(x)|dx (the shaded area in FIG. 5C). In FIG. 5A, each leaf opening is represented by a rectangle whose left and right ends are the positions of the MLC leaf pair and whose height is its beam-on time. The simplified intensity profile is created by stacking up these rectangles. Since all the leaf openings have the same beam-on time, i.e., the rectangles representing the leaf openings all have the same height, the resulting profile g(x) can have up to k upward edges and k downward edges, if we traverse the profile curve from left to right (FIG. 5B). This problem can be solved by searching for an optimal k-weight path in a graph capturing the geometry of the problem; the total cost of the path represents the error between the simplified profile and the input profile, and its weight indicates how many leaf openings are needed to create the simplified profile. FIG. 5C illustrates such a k-weight path, where the k upward edges are highlighted in red (solid if black and white) and the error is the area sum of the shaded regions.

(82) To find such a k-weight path, a directed graph G is constructed as in FIG. 5D. Specifically, for each possible height h of the rectangles, a grid structure is imposed, whose vertical edge lengths are h and horizontal edge lengths are of the resolution size of the given intensity patterns. Each grid node is a vertex of the graph G. The lower leftmost grid node is the source vertex s of G, and the lower rightmost node is the sink vertex t. For any horizontal grid edge, we put an edge in G from left to right with a zero weight and a cost that is the error incurred when this edge is used by the resulting profile (FIG. 5D) for a horizontal edge and its cost, i.e., the shaded area). For each vertical grid edge, we put in G an upward edge with a unit weight and a downward edge with a zero weight. Observe that a k-weight optimal s-to-t path in G thus constructed yields a desired simplified profile. This optimal path problem can be solved by the constrained shortest path algorithm.

(83) The k-link path algorithm above will convert each intensity profile into a simplified profile that can be deliverable by k leaf openings. For each simplified profile, there are potentially k! ways to break it up into leaf openings. In this algorithm, break each simplified intensity profile is broken into a set of canonical leaf openings. Specifically, a set of leaf openings is called canonical if only if for any two leaf openings [l.sub.i, r.sub.i] and [l.sub.j, r.sub.j] (where and l.sub.i and l.sub.j denote the left leaf positions, and r.sub.i and r.sub.j denote the right leaf positions), either l.sub.il.sub.i, rjr.sub.j, or l.sub.il.sub.i, r.sub.jr.sub.j. Intuitively, a set of canonical leaf openings can be sorted from left to right.

(84) FIGS. 6A-6C illustrate the key concept for the second step, i.e., for combining the canonical leaf openings into arcs. When combining the leaf openings to form a single-arc, for each pair of leaves, its single-arc can be viewed as two curves, each representing the leaf trajectory as a function of the leaf position with respect to the gantry angles. The solid curves in FIG. 6B show the corresponding leaf trajectories of the single-arc illustrated in FIG. 6A. If this single-arc is not deliverable under the maximum leaf speed constraint, the arc has to be adjusted to make it deliverable while minimizing the error incurred by the adjustment.

(85) Geometrically, the effect of the adjustment is to deform the original leaf trajectories into two new leaf trajectories. FIG. 6B gives such an adjustment where the original solid curves are changed to the dashed ones. The error is the area sum of the shaded regions. Since each leaf trajectory is a function of the leaf position with respect to the gantry angles, it can be viewed as a path of leaf positions along the gantry angle direction. This implies that the above adjustment problem can be solved by modeling it as a shortest path problem, in which the cost of a path is the error of the adjustment. FIG. 6C shows the graph construction. Each possible leaf position is a vertex, and two vertices for adjacent gantry angles are connected by an edge if they satisfy the maximum leaf speed constraint. Each vertex has a cost for the error incurred when adjusting the corresponding original leaf position for its gantry angle using that vertex. Geometrically, this error corresponds to a shaded region in FIG. 6B. Hence, the problem of adjusting a single arc as originally planned into a deliverable arc becomes a shortest path problem.

(86) The spacing of the apertures within each interval is also straightforward. This is because the apertures obtained for each angular interval can sorted from left to right. The angular interval can be evenly divided the by the number of apertures used to reproduce the intensity distribution. The apertures can be sequenced in such a way that: 1) the MLC leaves move in opposite directions in any two neighboring angular intervals; and 2) the two aperture shapes connecting any two angular intervals do not violate the physical constraints of the MLC, i.e., they are not so drastically different as to require large MLC movements. As the result, the shape-varying beam aperture slides back and forth while the gantry rotates around the patient. Since the apertures for different angular intervals are obtained with different dose rates, this single arc plan may require dose rate changes during the delivery.

(87) Leaf Position and Aperture Weight Optimization

(88) In some clinical cases, it may be desirable to construct a series of single-arc plans that represent a tradeoff between machine beam-on times and error between the delivered fluence and prescribed ideal fluences. In such a case, in the event that each of the previously described two methods fails to give a high quality plan, the following method described in this section may be used.

(89) Consider FIGS. 7A-7B, and, for simplicity, assume that the MLC consists of only one pair of leaves. FIG. 7A shows a sample single-arc plan, where the red curve represents the left leaf trajectory and the blue curve represents the right leaf trajectory. Note that, since, in a single-arc plan, the MLC keeps moving as the gantry rotates 360 around the patient at constant speed, the leaf trajectory is actually a functional curve between gantry angle and MLC leaf positions. For each small angular interval (typically)5-10, the portions of the leaf trajectories deliver a fluence profile (FIG. 7B).

(90) The above observation forms the basis for the following method:

(91) First, for each given error bound, the intensity profile in every planning beam interval for each pair of MLC leaves is converted to a set of candidate sequences of leaf openings using a shortest path algorithm with minimized error subject to the error bound. These candidate sequences may differ from each other in the starting and/or ending leaf openings. FIG. 8B shows a candidate sequence for the intensity profile as shown in FIG. 8A with certain starting and ending leaf trajectory positions. The goal here is to construct a graph whose nodes are the candidate leaf trajectories. Each node will have a cost associated with it, which is the error of the trajectory when delivering its own profile. Two nodes from adjacent angular intervals are connected together if their transitions are smooth. A shortest path here yields an optimal single-arc plan. To improve the running time, one limits the number of candidate trajectories. e.g., by restricting the trajectories to be monotonic.

(92) Second the sequences computed in the first step are connected together to form a single arc of leaf openings using a shortest path to ensure a smooth transition of the leaf positions between adjacent planning beam intervals while minimizing the total error incurred. Third, the single arcs for each pair of MLC leaves are then combined to form the final single-arc treatment plan.

(93) Since the above method can compute a single-arc plan subject to an error bound, the method can compute a tradeoff between error and number of control points, or error and machine beam-on times.

EXAMPLE 4

(94) Single Arc Sequencing

(95) Note that up to this point, the apertures are all at the designated planning angle at the center of the planning interval. When we move the aperture to another angle a few degrees away, the dose will change slightly. To maintain the dose delivered to the target, the apertures are adjusted as follows:

(96) In FIG. 9A, AB is the radiation source to rotational center i.e. isocenter, distance, and BC=x is the x coordinate of the right leaf. If the same opening is delivered at angle r away, the same opening will not be able to cover the same width of target as originally intended. To cover the same target width, the aperture needs to be enlarged by Dx. FIG. 9B omits DABC for clarity. From FIGS. 9A-9B, the following equation may be written:

(97) $\tan \left(+\right)=\frac{x.Math.\sin }{SAD-x.Math.\cos }.$
This yields:

(98) $x+x=SAD.Math.\tan \left(+\right)=SAD.Math.\frac{x.Math.\sin }{SAD-x.Math.\cos }.$
Substituting

(99) $=\frac{}{2}-,$
the following is obtained:

(100) $x-x=SAD.Math.\frac{x.Math.\sin \left(\frac{}{2}-\right)}{SAD+x.Math.\cos \left(\frac{}{2}-\right)}=SAD.Math.\frac{x.Math.\cos }{SAD-x.Math.\sin }.$
Similarly, the adjustment on the other side can be deduced. From FIGS. 9C-9D:

(101) $\tan \left(-\right)=\frac{x.Math.\sin }{SAD+x.Math.\cos }.$
This gives:

(102) $x-x=SAD.Math.\tan \left(-\right)=SAD.Math.\frac{x.Math.\sin }{SAD+x.Math.\cos }.$
Substituting

(103) $=\frac{}{2}-,$
the following is obtained:

(104) 0$x+x=SAD.Math.\frac{x.Math.\sin \left(\frac{}{2}-\right)}{SAD-x.Math.\cos \left(\frac{}{2}-\right)}=SAD.Math.\frac{x.Math.\cos }{SAD+x.Math.\sin }.$

(105) When the aperture is moved counterclockwise from the planned angle, r will be negative. Given these simple relationships, the new aperture widths can be set to provide the same coverage at the new angle as the original aperture provided at the planned angle. Alternatively or in addition to the above mentioned aperture shape adjustment for the apertures moved away from the planning angle, a simple aperture weight and shape optimization can be performed to further refine the single arc to deplete any potential rooms of improvement of the treatment plan quality.

EXAMPLE 5

(106) Single Arc Painting for Cancer of Larynx

(107) Sample plans were developed for several clinical cases. The plans were transferred to a Varian linear accelerator and delivered to a phantom. Comparison of the delivered and measured doses showed good agreement. One plan is for a larynx case with 3 targets, each with different dose specifications (FIG. 10A). FIG. 10B shows the dose distribution on a transverse slice at neck level resulting from the single-arc plan and FIG. 10C is the result of dose verification by delivering the single-arc plan to a phantom. Note that the phantom is different in size and shape from the patient and the calculated dose from the same plan is therefore also different.

THE FOLLOWING REFERENCES ARE CITED HEREIN

(108) 1. Bortfeld et al., Int J Rad Oncol Biol Phys, 28(3):723-730 (1994). 2. Boyer, A. & Yu, C., Seminars in Radiation Oncol 9(1):48-59 (1999). 3. Mackie et al., Med Phys, 20(6):1709-19 (1993). 4. Yu et al., Phys. Med. Biol., 40:769-787 (1995). 5. Yu, C. X., Phys. Med. Biol., 40:1435-49, (1995). 6.Yu et al., Int J Radiat Oncol Biol Phys 53(2):453-63 (2002). 7. Cho, P. S. & Marks, R. J. II, Phys. Med. Biol, 45(2):429-440 (2000). 8. Earl et al., Phys. Med. Biol. 48(8):075-89 (2003). 9. Cameron, C., Phys Med. 50(18):4317-36 (2005). 10. Shepard et al., Med. Phys. 34(2):464-470 (February 2007). 11. Brahme, A., Int J Radiat Oncol Biol Phys. 49(2):327-37 (2001). 12. Shepard et al., Physics in Medicine and Biology, 45(1): 69-90 (1999). 13. Webb, S., Phys. Med. Biol. 39(12):2229-2246 (1994).

(109) Any patents or publications mentioned in this specification are indicative of the level of those skilled in the art to which the invention pertains. Further, these patents and publications are incorporated by reference herein to the same extent as if each individual publication was specifically and individually incorporated by reference.

(110) One skilled in the art would appreciate readily that the present invention is well adapted to carry out the objects and obtain the ends and advantages mentioned, as well as those objects, ends and advantages inherent herein. Changes therein and other uses which are encompassed within the spirit of the invention as defined by the scope of the claims will occur to those skilled in the art.