Journal article
GEOMETRIC ALGORITHMS FOR STATIC LEAF SEQUENCING PROBLEMS IN RADIATION THERAPY
International journal of computational geometry & applications, Vol.14(4n05), pp.311-339
10/2004
DOI: 10.1142/S0218195904001494
Abstract
The static leaf sequencing (SLS) problem arises in radiation
therapy for cancer treatments, aiming to accomplish the delivery of a
radiation prescription to a target tumor in the minimum amount of
delivery time. Geometrically, the SLS problem can be formulated as a
3-D partition problem for which the 2-D problem of partitioning a
polygonal domain (possibly with holes) into a minimum set of monotone
polygons is a special case. In this paper, we present new geometric
algorithms for a basic case of the 3-D SLS problem (which is also of
clinical value) and for the general 3-D SLS problem. Our basic 3-D SLS
algorithm, based on new geometric observations, produces guaranteed
optimal quality solutions using O(1) Steiner points in polynomial
time; the previously best known basic 3-D SLS algorithm gives optimal
outputs only for the case without considering any Steiner points, and
its time bound involves a multiplicative factor of a factorial function
of the input. Our general 3-D SLS algorithm is based on our basic
3-D SLS algorithm and a polynomial time algorithm for partitioning a
polygonal domain (possibly with holes) into a minimum set of x-monotone
polygons, and has a fast running time. Experiments of our SLS algorithms
and software in clinical settings have shown substantial improvements
over the current most popular commercial treatment planning system and
the most well-known SLS algorithm in medical literature. The
radiotherapy plans produced by our software not only take significantly
shorter delivery times, but also have a much better treatment quality.
This proves the feasibility of our software and has led to its clinical
applications at the Department of Radiation Oncology at the University
of Maryland Medical Center. Some of our techniques and geometric
procedures (e.g., for partitioning a polygonal domain into a minimum set
of x-monotone polygons) are interesting in their own right.
Details
- Title: Subtitle
- GEOMETRIC ALGORITHMS FOR STATIC LEAF SEQUENCING PROBLEMS IN RADIATION THERAPY
- Creators
- DANNY Z Chen - University of Notre DameXIAOBO S HU - University of Notre DameSHUANG (SEAN) Luan - University of Notre DameCHAO Wang - University of Notre DameXIAODONG WU - University of Texas–Pan American
- Resource Type
- Journal article
- Publication Details
- International journal of computational geometry & applications, Vol.14(4n05), pp.311-339
- Publisher
- World Scientific Publishing Company
- DOI
- 10.1142/S0218195904001494
- ISSN
- 0218-1959
- eISSN
- 1793-6357
- Language
- English
- Date published
- 10/2004
- Academic Unit
- Electrical and Computer Engineering; Radiation Oncology; The Iowa Institute for Biomedical Imaging
- Record Identifier
- 9984197524602771
Metrics
3 Record Views