An optimal algorithm for configuring delivery options of a one-dimensional intensity-modulated beam

The problem of generating delivery options for one-dimensional intensity-modulated beams (1D IMBs) arises in intensity-modulated radiation therapy. In this paper, we present an algorithm with the optimal running time, based on the 'rightmost-preference' method, for generating all distinct delivery options for an arbitrary 1D IMB. The previously best known method for generating delivery options for a 1D IMB with N left leaf positions and N right leaf positions is a 'brute-force' solution, which first generates all N! possible combinations of the left and right leaf positions and then removes combinations that are not physically allowed delivery options. Compared with the brute-force method, our algorithm has several advantages: (1) our algorithm runs in an optimal time that is linearly proportional to the total number of distinct delivery options that it actually produces. Note that for a 1D IMB with multiple peaks, the total number of distinct delivery options in general tends to be considerably smaller than the worst case N!. (2) Our algorithm can be adapted to generating delivery options subject to additional constraints such as the 'minimum leaf separation' constraint. (3) Our algorithm can also be used to generate random subsets of delivery options; this feature is especially useful when the 1D IMBs in question have too many delivery options for a computer to store and process. The key idea of our method is that we impose an order on how left leaf positions should be paired with right leaf positions. Experiments indicated that our rightmost-preference algorithm runs dramatically faster than the brute-force algorithm. This implies that our algorithm can handle 1D IMBs whose sizes are substantially larger than those handled by the brute-force method. Applications of our algorithm in therapeutic techniques such as intensity-modulated arc therapy and 2D modulations are also discussed.