Journal article
An optimal algorithm for configuring delivery options of a one-dimensional intensity-modulated beam
Physics in medicine & biology, Vol.48(15), pp.2321-2338
2003
DOI: 10.1088/0031-9155/48/15/306
PMID: 12953901
Abstract
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.
Details
- Title: Subtitle
- An optimal algorithm for configuring delivery options of a one-dimensional intensity-modulated beam
- Creators
- Shuang (Sean) Luan - Department of Computer Science and Engineering, University of Notre Dame, Notre Dame, IN 46556, United StatesDanny Z CHEN - Department of Computer Science and Engineering, University of Notre Dame, Notre Dame, IN 46556, United StatesLi Zhang - Department of Computer Science and Engineering, University of Notre Dame, Notre Dame, IN 46556, United StatesXiaodong Wu - Department of Computer Science, The University of Texas-Pan American, Edinburg, TX 78539-2999, United StatesCedric X YU - Department of Radiation Oncology. University of Maryland School of Medicine, 22 South Greene Street, Baltimore, MD 21201-1595, United States
- Resource Type
- Journal article
- Publication Details
- Physics in medicine & biology, Vol.48(15), pp.2321-2338
- Publisher
- Institute of Physics; Bristol
- DOI
- 10.1088/0031-9155/48/15/306
- PMID
- 12953901
- ISSN
- 0031-9155
- eISSN
- 1361-6560
- Language
- English
- Date published
- 2003
- Academic Unit
- Electrical and Computer Engineering; Radiation Oncology; The Iowa Institute for Biomedical Imaging
- Record Identifier
- 9984047879902771
Metrics
22 Record Views