WO2008130634A1 - Single-arc dose painting for precision radiation therapy - Google Patents

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.

Description

SINGLE-ARC DOSE PAINTING FOR PRECISION RADIATION THERAPY

Federal Funding Leαend

This work was supported by grant CA11799 from the National Institutes of Health. The U.S. Government has certain rights in this invention.

BACKGROUND OF THE INVENTION

Field of the Invention

The present invention relates to the field of radiation oncology for malignant tumors and the like. Specifically, the present invention provides methods and systems for planning delivery of radiation therapy by means of a single-arc dose of radiation.

Description of the Related Art

Conformal radiation therapy is an important procedure available to the physician for the treatment of malignant tumors. Such therapy is used for eradicating or shrinking tumors that are relatively inaccessible to other modes of treatment such as surgical excision. However, because the ionizing radiation that is administered is damaging to both healthy and malignant tissue, it is important to confine the effect of the irradiation to the target tissue, to the extent possible, while sparing the adjacent tissue by minimizing irradiation thereto. To achieve this goal, various techniques of irradiating a target tumor with a defined beam of ionizing radiation have been devised.

Although simple masking techniques using radiation absorbing materials have some utility, techniques using radiation beams directed at the target tissue from various angles about a patient have come to be preferred because they have the advantage of reducing the burden of radiation on overlying tissue and of permitting a more conformal irradiation of an internal mass of irregular shape, possibly intimately involved with adjacent healthy tissue. Such beams are often provided from a radiation source, e.g., x-ray photons or high- energy electrons, mounted on a rotating gantry, that allows the radiation source to be revolved in a generally circular path while providing a beam of radiation directed generally at the isocenter of such a path. A patient is positioned within the circular path, preferably with the tumor located, to the extent possible, at the isocenter for receiving the maximum dose of radiation as the source is revolved. The cross-sectional shape and size of the radiation beam is typically varied as the source is positioned at different angles by rotation of the gantry in order to assure, to the extent possible, that the radiation is incident on the tumor itself and not on adjacent healthy tissue. Similarly, the intensity of the beam can be varied within the cross-sectional area in order to optimize the distribution of absorbed radiation within the tumor.

A number of techniques have been developed with the intention of providing for maximum absorption of radiation within the tumor while minimizing exposure of adjacent healthy tissue. Intensity-modulated radiation therapy (IMRT) was developed based on the principle that for a given tumor, there is a set of preferred ways to direct the radiation to it. More radiation can be sent through some beam angles than others and within the same beam angle, there are preferred locations through which the radiation is directed to the tumor. Computer-assisted treatment planning systems have been developed to take advantage of such preferred angles and locations, e.g., by varying the intensity of the radiation beam across the radiation fields, in order to accomplish better treatment regimens.

Consequently, intensity-modulated radiation therapy (IMRT) has been widely adopted as a new tool in radiation therapy to deliver high doses of radiation to the tumor while providing maximal sparing of surrounding critical structures. Both rotational and gantry-fixed IMRT techniques have been implemented clinically using dynamic multileaf collimation (DMLC) (1-6).

In gantry-fixed IMRT, multiple radiation beams at different orientations, each with spatially modulated beam intensities, are used (1-2, 4). The beams may be administered to the patient in a single transverse plane as the source revolves around the patient (coplanar) or may be shifted axially with respect to the patient (non-coplanar). Rotational IMRT, typically administered by a continuously revolving source that is also moved axially along the patient, as it is currently practiced, mainly employs temporally modulated fan beams (3). Although the quality of IMRT treatment plans has steadily improved, the plans tend to be relatively complicated, which makes for a somewhat inefficient delivery of treatment. Consequently, labor-intensiveness has been one of the drawbacks of IMRT. Furthermore, in general, a large number of different complex field shapes is often needed, which also compromises the efficiency of the treatment and can result in an increased number of collimator artifacts (7). Nevertheless, while long-term clinical results of IMRT treatments are still limited, initial results appear very promising, and with increased use of IMRT, more encouraging results are emerging.

U.S. Patent 5,818,902 to Yu teaches the use of overlapping multiple arcs to deliver modulated beam intensities around the patient which is called intensity-modulated arc therapy (IMAT). Delivery of the radiation during overlapping multiple arcs achieves modulated beam intensities at all angles around the patient (5-6). However, IMAT has not been widely adopted for clinical use. In IMAT, the intensity distributions are first optimized using a treatment planning system for tightly-spaced beam angles every 5-10 degrees all around the tumor. These intensity distributions are then approximated by a stack of uniform intensity segments with different cross sectional shapes. These stacks of uniform beam segments at all beam angles are then sequentially administered as the radiation source describes multiple rotational arcs while the beam cross sections are defined at each angular position by a multi-leaf collimator (MLC) with its leaves moved by a computer-programmed controller to provide a sequence of predetermined apertures.

The inverse planning procedures used to determine beam cross- sections and intensities when planning IMRT and IMAT treatments have typically required the user to pre-determine the number of beams to use and their orientations. This limitation can significantly affect the quality of the treatment plans because the most preferred angle might be completely missed. Rotational IMRT does not have such problems since all angles are considered in the plan. Furthermore, because the delivery of IMAT requires the use of multiple (4 - 11) arcs, each of which may take 1 to 2 minutes to deliver, the total treatment time is similar to that of fixed beam IMRT treatments. It is also relevant that, even when intensity distribution is determined for densely-spaced beam angles, i.e., 5 to 10 degrees, and sequenced for delivery in a limited number of multiple arcs, the resultant distribution of radiation absorption in the tumor can still only approximate that which would be provided by optimized beam intensities and cross-sections, because each of the planned beams may require significant variations that cannot be accommodated by the plan as executed by the equipment. As a result, the final IMAT plan is almost always degraded from the unconstrained optimized plan.

One attempt to solve this problem is a method for optimizing IMAT using Direct Aperture Optimization, in which the shape and weight of the apertures contained in one or more arcs are optimized simultaneously (8). A similar method ( 9), who showed that a single arc optimization using a method similar to Direct Aperture Optimization could generate satisfactory treatment plans for a simple case. In both methods, a limited number of beam angles were used to illustrate the principle. For complicated cases, single-arc optimization over a limited number of angles cannot generate plans that rival fixed-beam IMRT plans (8). Using such methods, it is prohibitive with today's technology to optimize the rotational delivery with more beam angles, because pencil beams must be calculated for all the beam angles (8-9).

Another concern with current radiation treatment planning methods is that no method developed hitherto can create a rotational IMRT plan that consistently rivals fixed beam IMRT without requiring beam intensity modulation. For simple cases it was demonstrated that a single optimized arc can yield results as good as those of fixed-field IMRT, while, for more complicated cases, such as head and neck cases with multiple targets, such an approach would not work well, and intensity modulation is required (8). Although allowing the planned dose rate to vary with gantry angle provides a new degree of freedom, such relaxation of a restraint is not sufficient in itself to establish that a single arc using the described optimization method can replace multiple-arc IMAT. Treatment planning using current optimization schemes requires intensity modulation consistently to rival fixed beam IMRT (10).

Thus, there is a recognized need in the art for improved radiation therapy planning methods that enable greater efficiency in delivery of radiation therapy. More specifically, the prior art is deficient in methods and systems for single-arc dose radiation therapy. The present invention fulfills this long-standing need and desire in the art.

SUMMARY OF THE INVENTION

The present invention is directed to a method for designing a radiation treatment for a subject using single arc dose painting. The method comprises providing an unconstrained optimization map which supplies intensity profiles of densely-spaced radiation beams and aligning each intensity profile to a pair of multiple leaf collimation (MLC) leaves. A shortest path algorithm is applied to convert each pair of MLC leaves to a set of leaf aperture sequences, where each set of leaf aperture sequences forms a shortest path single arc thereof andeach single arc of leaf apertures is connected to form a final treatment single arc, thereby designing the single arc dose painting radiation treatment. The present invention is directed to a related method further comprising 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. The present invention is directed to another related method further comprising adjusting a shape of the aperture as a radiation dose delivery angle changes along the final treatment single arc to keep the dose constant.

The present invention also is directed to a method for irradiating a tumor in a subject. The method comprises delivering a continuous dose of radiation to the tumor through sets of multiple leaf collimation (MLC) aperture sequences during a single rotation along one or more treatment single arc paths. The present invention is directed a related method comprising further adjusting the aperture shape as described supra. The present invention is directed to another related method where, prior to delivering the radiation dose, the method further comprises steps of providing an unconstrained optimization map which supplies intensity profiles of densely-spaced radiation beams and 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 the set of leaf aperture sequences and connecting each single arc of leaf apertures to form the final treatment single arc.

The present invention is directed further to a system for delivering radiation treatment using single arc dose painting. The system comprises 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, said shortest path algorithm converting each pair of MLC leaves to a set of leaf aperture sequences forming a shortest path single arc thereof, such that 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. The present invention is directed a related system where the shortest path algorithm further comprises adjusting the aperture shape as described supra. The present invention is directed further still to a computer-readable medium tangibly storing an algorithm to determine a final single arc path for a single arc dose painting radiation treatment. The algorithm enables 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 each are aligned to an intensity profile of densely-spaced radiation beams, and to connect each single arc of leaf apertures to form a final treatment single arc. The present invention is directed a related computer-readable medium where the shortest path algorithm further enables adjusting the aperture shape as described supra. The foregoing has outlined rather broadly the features and technical advantages of the present invention in order that the detailed description of the invention that follows may be better understood. Additional features and advantages of the invention will be described herein, which form the subject of the claims of the invention. It should be appreciated by those skilled in the art that any conception and specific embodiment disclosed herein may be readily utilized as a basis for modifying or designing other structures for carrying out the same purposes of the present invention. It should also be realized by those skilled in the art that such equivalent constructions do not depart from the spirit and scope of the invention as set forth in the appended claims.

The novel features which are believed to be characteristic of the invention, both as to its organization and method of operation, together with further objects and advantages will be better understood from the following description when considered in connection with the accompanying figures. It is to be expressly understood, however, that any description, figure, example, etc. is provided for the purpose of illustration and description only and is by no means intended to define the limits the invention.

BRIEF DESCRIPTION OF THE DRAWINGS

Figures 1A-1C illustrate how to flip the monotone decreasing path p_r to a monotone increasing path p ^' _r (Figure 1 A), how to flip two monotone decreasing paths p, and p_r to two monotone increasing paths p^' ₇ and p^' _r (Figure 1B) and how the xy-monotone region enclosed by the two paths p^' ₇ and p\ in Figure 1B corresponds to a sequence of n vertical bars 8₁,6₂, ■ ■ ■ ,S_n (Figure 1C). Note that after the flipping operations in Figures 1A-1 B, neither the steepness nor the closeness constraint is violated, and l_iιPlιPr = \_{>ιP \ιP}-_r holds for every i, which implies that the total error remains the same.

Figures 2A-2D illustrate the transformation of G^' into ^"6 (Figures 2A- 2B) and the layered DAGs G_{;1 ;}i₊₁, G_/1|/1+2) and G_{/1 n} (Figure 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 GM after merging the DAGs G,-_1i/1+1, G,_{1 |/1+2}, and G_n/I (Figure 2D).

Figures 3A-3C illustrate the geometry of the vertex layer U₁ of the DAG G^' for l_start< i ≤ r_start, r_staft < i ≤ /^, and I^ < i < r^. In each figure, all vertices in the vertex layer L₁ (or L^',) 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.

Figures 4A-4B illustrates sliding window leaf sequencing. In Figure 4A the desired intensity profile is aligned with a leaf pair. Figure 4B shows separated intensity profiles to be conformed by the leading (right) and training

(left) leaves. Figure 4C shows adjusted leaf traveling trajectories after considering the physical constraints of leaf travel.

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

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

Figures 7A-7B illustrate the planning of a single arc dose painting. Figures 8A-8 B illustrate leaf position and aperture weight optimization using the shortest path graph algorithm.

Figures b illustrate field width adjustment on the right side (b) and on the left side (Figures 9C-9D).

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

DETAILED DESCRIPTION OF THE INVENTION

I. Definitions

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. 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." 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.

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

II. Present Invention 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. 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 to keep the dose constant.

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.

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.

In another embodiment of the present invention there is provided a method for irradiating a tumor in a subject, comprising delivering a continuous dose of radiation to the tumor through sets of multiple leaf collimation (MLC) aperture sequences during a single rotation along one or more treatment single arc paths.

Further to this 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. In another further embodiment prior to delivering the radiation dose, the method may comprise 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 the set of leaf aperture sequences; and connecting each single arc of leaf apertures to form the final treatment single arc. In this further embodiment 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.

In both embodiments each set of MLC aperture sequences may form a shortest path single arc thereof, where the sets are connected to form a shortest path treatment single arc. Also, the paths of more than one single arc may be non-coplanar. In addition the apertures may slide back and forth along the single arc path during delivery of the radiation dose. Furthermore, multiple leaf collimation may be dynamic. In yet 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.

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 thereby keeping the dose constant. 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.

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 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.

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 amy 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. 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.

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.

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.

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. 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. 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.

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.

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.

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 responsvie to such treatment. As is known in the art such devices comprise at least a source of radiation, amoveable, rotatable gantriy, 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 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 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.

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

Constrained Coupled Path Planning (CCPP)

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 n x H uniform grid R₉, a non-negative function f defined on the integers in {1, 2, . . . , n}, and positive integers l_start, r_stari, len_d, i"en_d> c, and Δ (Δ ≤ H), find two noncrossing paths p_/ and p_r of height H along the edges of R_g to minimize the total error ε(p_/; p_r) Δ =

- f{i)l subject to the following constraints: (1) p, (resp., pr) starts at (/_størt, 0) (resp., (r_start, O)) and ends at (/^, H) (resp., (A^, H)), (2) (the steepness constraint) both p, and p_r are c- steep paths, and (3) (the closeness constraint) \l_i<fAιf)r - f{i)\ < Δ for all / = 1 , 2 n.

Without loss of generality, it is assumed that l_start ≤ len_d and r_start < r^ so that the two sought paths p_/ and p_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-1 B) one or both of the optimal paths for this new problem, two optimal paths are obtained for the original CCPP problem.

Algorithm for the case where I₃₁, ≥ r_start

It is to be noted that the algorithm can be adapted easily to handle the other case in which I_6n^ < r_start. The region P(p_h p_r) is a rectilinear xy-monotone polygon in R₉ 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, U₁, U₂ U_n, which are defined as follows to satisfy the additional geometric constraints of the CCPP problem: r {[a,β\^{i)\a = β=0anά\β-a-f(i)\^<Δ} if1≤/≤W

{[α, β\ ^w I 0 = α < β ≤ H - c and \β - α - f(i)\ < Δ} if l_start < i ≤ r_start

Ui {[α.0 ( V0) I c ≤ α < β ≤ H - c and \β - α - f{i)\ < Δ} if r_start <i≤l_enα

<

\β - α - f{i)\ < Δ} if l_βni<i≤ r_end

{[α, β\ ( ^v0^> I α = β=Hand \β-α-f{i)\ <Δ} ifr_end< \≤n

Eq. (1)

The^" weight of a [α, /?l ^(/) is defined as ω^'([α, )3] ^w) = \β - α - 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 GO 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(O₁H), D(α,β) (0 < α < β < H), O{Q,β) (0 < β < H), and D(O, 0). Thus the shortest path computation can be sped up and the CCPP algorithm takes O(πHΔ) time.

EXAMPLE 2

Computing the complete set of all CCPP problem instances Overview of the algorithm

Given f, n, H, Δ, and c, CCPP problem instances are solved on f, n, H, Δ, C₁ Istar_t, r_stan, len_d, and r^ for all possible combinations of l_start, r_sm, /^, and r^.

Without loss of generality, only those combinations which satisfy l_start < I_6nO and rstar_t ^{≤ r}en_d ^are considered. All problem instances are classified into two subsets

S₁ and S₂, with S₁ (resp., S₂) containing those with I₆^ ≥ r_start (resp., I^ < r_start).

Solving all CCPP instances in Si

It is to be noted that this approach can be adapted easily to solve all instances in S₂. Since 0 ≤ l_start ≤ r_start < I^ < r^ ≤ n, there are totally N = Θ(n⁴) problem instances, denoted by I₁, I₂, . . . , I_N. Let l^(k) _star_t. ^ star_t, ^^k)end- and /^^k) _end be the corresponding specification for the problem instance Ik. An instance I_k (1 ≤ k ≤ N) corresponds to a shortest path problem on a vertex-weighted DAG, denoted by G\, of O(nHA) vertices and O(nH²A²) edges. The key observation is that G^' _k can be transformed into an edge-weighted DAG, denoted by ^"G^₁ with only O(Δ) vertices and 0(A²) edges.

The algorithm consists of two main steps. First, prepare the weights of all edges in ^'G₁, ^'G₂ and ^'G_N (0(A²) edges for each ^"G*). The weights of all the O(n⁴A²) edges are implicitly computed and stored in a batch fashion, in totally O(n²H²) time, such that for any edge, its weight can be reported in 0(1) time. Second, a shortest path is computed in ^'G₁, ^'G₂, . . . , and ^'G_N, respectively. It is shown that each ^"G_k (1 ≤ k ≤ N) is a DAG satisfying the Monge property (1-2,4). Since the weight of any edge can be obtained in 0(1) time, a shortest path in ^ΛG_k takes only 0(A) time to compute. The algorithm thus takes O(n²HA² + P⁴A) time, improving the straightforward 0(n⁵HA) time algorithm, i.e., applying the CCPP algorithm N = O(n⁴) times) by a factor of min{π/-/, n³/Δ}.

The graph transformation

For fixed l_start, /^, r_start, and r^ (0 ≤ l_start ≤ r_start ≤ I^ ≤ r^ < n), let / be the corresponding CCPP problem instance and G^' = (V(G^').E(G^')) be the vertex- weighted DAG defined in Example 1 for solving /. 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) = ∑u is elemen_t of p o)^'(u). For u, v is an element of V(G^'), denote by π^'(υ, v) a shortest u-to-ι/ path in G^'. An edge-weighted directed graph ^"G = (V(^'G),E(^'G)) is constructed from G^' as follows (Figs. 2A-2B). The vertex set VfG) is a subset of V(G^"), and consists of two dummy vertices s and f and four vertex layers:

L* = ¹L,,' L* = L'_Tjtατi, L₃ = £L*+i> and U = i'r.^+i-

The edge set E(^"G) is simply U6-₁& * XH-O U (W X ZI) u [U * {*}). 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 ^"CU(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) = +°° if there is no path from u to v in G ^'.

^"G is an edge-weighted DAG and has O(Δ) vertices and O(A²) edges (by the definition of L^'j in Example 1). Define the weight ^"ω (p) of a path p in ^"G as _Λ ^"ω (p) = ∑e is _an elemen_t o_f p ^* ω (©)• A shortest s-to-f path in G ^' is closely related to a shortest s-to-t path in ^"G. In fact, it is not difficult to show that tf p^' = s -→ U₁ → u₂ ^{→ • • •} → U_n → t is a shortest s-to-f path in G', then ^"p = s → Uι_staΛ → u_rstart → u_/end+1 → Urencn-: → f is a shortest s-to-f path in ^"G₁ with ^'w(^'p) = w^'(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 → ^ → ι/₂ → ι/₃→ ι/₄ → / is a shortest s- to-t path in ^"G, then

is a shortest s-to-f path in G^'.

Before explaining why the vertex layers L ^',_stali, L^' _rstart, L^' _/e/7dt1, and /_ ^'reπ_d+i from G^' for the construction of ^"G were chosen, Equation (1) must be reviewed. Observe that if / is fixed and l_start, r_start, I en_d, and r^ are temporarily viewed as parameters, then Equation (1) implies that the /-th vertex layer in any G'_k (1 < k < N) is in exactly one of five possible states, denoted by Λj^(l), Λ j^(ll), Λi^(lll), Λi^(IV), and Λi^(V), e.g., Λi^(l) if 1 < / < l_start). For a fixed k (1 < k < N), in the DAG G\, the /-th vertex layer L is of type I if L = Λj^(l). The type II, III, IV, and V vertex layers are defined similarly. Clearly, in the DAG G^', all vertex layers between s and L ^'y_sra/τ, L ^' _Istan and L ^arson, L ^' nan and I ^'/eπd+i. ^ ^' lend_* \ and ^ ^'reπd+i. and I ^' _reπd+1 and f 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₁, ^"G₂, . . . , ^'G_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.

Computing the edge weights for all transformed DAGs

It is demonstrated herein how to compute the weights of all edges in the transformed DAGs ^"6,, ^"G₂, . . . , ^'G_N. Recall that the weight of an edge in ^"G_fc corresponds to a one-pair shortest path problem instance on G ^' _k. Since every ^"G^ has O(A²) edges, there are in total O(n⁴Δ²) edges in ^"G₁, ^"G₂, . . . , ^'G_N, corresponding to O(π⁴Δ²) one-pair shortest path problem instances.

It is stated that the O(n⁴Δ²) edges actually correspond to only O(n²A²) 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_k, denote by SP(u, v, k) the corresponding one-pair shortest path instance, i.e., finding a shortest w-to-v path in G^' _k. Considering the indices of the vertex layers in which u and v lie in ^"G_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_k is discussed. For this case, let Z₁ = ^s_tan and /₂ = f^k)en_{d +} i; then u is an element of Aⁿn C V(G ^' _k), v is an element of A^N _i2 C V(G^' _k), and all vertex layers between u and v in G^' _k are of type III (Fig. 2A). Let G_i1ii2 be a layered DAG whose vertices consist of the vertex layers A¹¹ _Z1, A¹¹Vi₊₁, A¹¹¹ _Z1+2, . . . , A¹Vi, and A^z₂. in this order, and whose edges are defined based on the same domination relation D(-, ^■).

Clearly, SP(u, v, k) is equivalent to finding a shortest u-to-v path in Gj_{1 J2}. Since I₁ (resp., i2) ranges from 1 to n, G_{11 J2} has O(n²) possible choices. Note that u (resp., v) belongs to the layer A¹¹ _Z1 (resp., A¹⁷ _Z2), which contains O(Δ) vertices for any Z₁ (resp., /₂). It follows that SP(u, v, k) has O(n⁴A²) possible choices for the case where u (resp., v) lies in the 2nd (resp., 3rd) layer of ^"G_k. Other cases can be analyzed similarly. Since there are five cases, SP(u, v, k) has O(n²A²) x O(1) = O(n²A²) possible choices in total. Since there are only O(n²A²) distinct one-pair shortest path problem instances, it is preferred to implicitly compute and store the weight of each edge of ^'G₁, ^'G₂ ^'G_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*, its weight can be reported in 0(1) time. It is demonstrated how to solve the O(n²Δ²) 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 GMJ₂ (as defined in the previous paragraph) for all Z₁, Z₂. Each instance is specified by a source vertex u is an element of Λ^π _/i and a destination vertex v is an element of A¹⁷ _Z2- Recall that Gj_{1 J2} contains the vertex layers A¹¹ _Z1, A¹¹¹ _ZHi, A¹¹¹ _Zi₊₂, • ■ • . A¹Vi. and A¹⁷ _Z2, For a fixed Z₁, the layered DAGs Gj_{1 ii2}, for all Z₂ = Z₁ + 1 n, can be merged into one DAG, simply denoted by Gzi (Figs. 5C-5D). For any vertex u is an element of A¹¹ _Z1, its single-source shortest paths can be computed in G₁₁, in O(nHA) time as in the CCPP algorithm. Since IA¹¹ _Z1I = 0(A) and Z₁ ranges from 1 to n, the one-pair shortest path instances in

can be solved for all Z₁, Z₂, in O(nHA) x O(n) x O(Δ) = O(n²Δ²) time.

Shortest path computation on the transformed DAGs

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.

Consider the vertex layers T₂ and ^"L₃ of ^"G. Clearly, ^"L₂ = L^' _rstart = {[α,

| 0 < β <= H - c and \β - f(rstart)\ ≤ Δ}. Thus ^'L₂ can be written as ^'L₂ = (U₁, U₂, . . . , Uy^), where u_k = [0,

and 0 < # < /32 < • • • < $-_L2| ≤ H - c. Similarly, write "L₃ as "L₃ = {v_h V₂ vju,}, where v_k = L_k.H/^/eπd+1)(1 ≤ k ≤ |1₃|) and c ≤ O₁ < α₂ < ^{• • •} < α_yL2] <

H. The following lemma shows the properties of the edges from the vertices on "L₂ to "L₃ in ^"G. Lemma: (A) Let u, (resp., vj) be a vertex on ^"L₂ (resp., ^"L₃) of ^"G, with 1 < / < |^"L₂| (resp., 1 ≤j ≤ |^"L₃|). If 'ωtø, Vy) = 1 , then for any ;^' < j (resp., /^' > /), "ω (u_/, V₇ ) = ∞ (resp., ^"ω (w,-, »/,) = ∞). (B) Let U₁, u_r (resp., v_Jt v_}) be two vertices on "L₂ (resp., ^"L₃) of ^"G, with 1 < i < /^' < |^"L₂| (resp.,1 < \ < j^' ≤ |^"L₃|). If both edges O₁ = (u_h Vj ) and e₂ = (u,-, f_y) have finite weights, then edges e₃ = (u,, vj) and e₄ = (u,- v_y ) also both have finite weights. Moreover, "ω (e₃)+ ^"ω (e₄) "ω (eθ+ ^"ω (e₂).

The lemma implies that the matrix A of size |^"L₂| x |^"L₃|, with A_j = "(» (Uj, Vj), is a Monge matrix. Note that for any / and ;, ^"ω (U₁, vj) can be reported in 0(1) time as described above. Thus in ^"G, once the shortest paths from s to all vertices in ^"L₂ are computed, using the Monge matrix multiplication algorithms [1 , 2, 4], the shortest paths from s to all vertices in ^"L₃ can be computed in 0(A) time. Observe that outside the subgraph of ^"G between the vertex layers ^"L₂ and "L₃ (Fig. 2B), there are only O(Δ) edges of ^"G. Hence a shortest s-to-t path in ^"G can be computed in 0(A) time. Thus, the following theorem is: Given a non-negative function f 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²H ²+n4 ) time.

EXAMPLE 3 Unconstrained intensity optimization in single-arc dose painting

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

Leaf-sequencing in single-arc dose painting

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.

Line segment approximation to component intensity profiles

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.

The conversion from fluence distributions to MLC "sliding window" delivery is illustrated by Figures 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 Profile - Leading profile.

The separated profiles become the leading and trailing leaf positions as functions of time. If both leaves are moved according to Figure 1B, the desired intensity profile will be created. Inspection of Figure 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.

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 borrowed from computer science. 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.

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.

Leaf position and aperture weight optimization 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.

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: 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.

Figures 5A-5D illustrate the key idea of this step. In Fig. 5A, the optimized fluence profile is represented by the functional curve f(x) and the resulting simplified profile is the rectilinear functional curve g(x) that is deliverable by /c=4 leaf openings with equal beam-on. The error here is the integral of the absolute difference between the two functions, 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 /c-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 /(-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.

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 /c-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.

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 [/,, r] and [I_j, ή\ (where /, and /_y denote the left leaf positions, and r, and η denote the right leaf positions), either l,≤l_h η-≤η, or l,≥l,, η≥η. Intuitively, a set of canonical leaf openings can be sorted from left to right.

Figures 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.

Geometrically, the effect of the adjustment is to deform the original leaf trajectories into two new leaf trajectories. Figure 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. Figure 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 Figure 6B. Hence, the problem of adjusting a single arc as originally planned into a deliverable arc becomes a shortest path problem.

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.

Leaf position and aperture weight optimization

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.

Consider Figures 7A-7B, and, for simplicity, assume that the MLC consists of only one pair of leaves. Figure 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).

The above observation forms the basis for the following method: 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. Figure 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.

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.

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

Single Arc Sequencing 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:

In Figure 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. Figure 9B omits DABC for clarity. From Figs. 9A-9B, the following equation may be written:

This yields: x + Δx = SAD ^• tan(p + Δp )= SAD ^^ .

SAD - x -cosy

Substituting γ = — -θ , the following is obtained:

Similarly, the adjustment on the other side can be deduced. From Figures 9C- 9D: x - siny tan(p - Δp)= SAD + x -cosy This gives:

x - Ax = SAD ^• tan(p - Δp)= SAD ^^

SAD + x -cosy

Substituting γ = — - θ , the following is obtained:

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

Single arc painting for cancer of larynx 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). Figure 10B shows the dose distribution on a transverse slice at neck level resulting from the single-arc plan and Figure 1OC 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.

1. Bortfeld et al., lnt 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., lnt 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 (Feb 2007).

11. Brahme, A., lnt 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).

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.

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.

Claims

WHAT IS CLAIMED IS:

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, thereby designing the single arc dose painting radiation treatment.

2. The method of claim 1 , further comprising: 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.

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 single arc to keep the dose constant.

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. A method for irradiating a tumor in a subject, comprising: delivering a continuous dose of radiation to the tumor through sets of multiple leaf collimation (MLC) aperture sequences during a single rotation along one or more 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 to keep the dose constant.

12. 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.

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

14. The method of claim 10, wherein the apertures slide back and forth along the single arc path during delivery of the radiation dose.

15. The method of claim 10, wherein prior to delivering the radiation dose, the method comprises: 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 the set of leaf aperture sequences; and connecting each single arc of leaf apertures to form the final treatment single arc.

16. The method of claim 15, 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.

17. The method of claim 10, wherein multiple leaf collimation is dynamic.

18. 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; structure for generating an unconstrained optimization map of intensity profiles of densely-spaced radiation beams; structure for aligning each intensity profile to a pair of multiple leaf collimation (MLC) leaves; and structure for applying a shortest path algorithm, said shortest path algorithm converting each pair of MLC leaves to a set of leaf aperture sequences forming a shortest path single arc thereof, said shortest path algorithm further connecting each single arc of leaf apertures to form a final treatment single arc effective for single arc dose painting.

19. The system of claim 18, the shortest path algorithm further adjusting a shape of the leaf aperture as a radiation dose delivery angle changes along the final treatment single arc thereby keeping the dose constant.

20. The system of claim 18, wherein the shortest path 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.

21. The system of claim 18, wherein the multiple leaf collimator is dynamic.

22. 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 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.

23. The computer-readable medium of claim 22, 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 thereby keeping the dose constant.

24. The computer-readable medium of claim 22, 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.