This paper presents a leaf sequencing software called SLS (static leaf sequencing) for intensity-modulated radiation therapy (IMRT). SLS seeks to produce improved clinical IMRT treatment plans by (1) shortening their treatment times and (2) minimizing their machine delivery errors. Our SLS software is implemented using the C programming language on Linux workstations and is designed as a separate module to complement the current commercial treatment planning systems. The input to SLS is discrete radiation intensity maps computed by current planning systems, and its output is (modified) optimized control sequences for the radiotherapy machines. Our SLS approach is very different from the commonly used planning methods in medical literature in that it is based on graph algorithms and computational geometry techniques. Comparisons of SLS with the CORVUS commercial planning system indicated that for the same set of discrete radiation intensity maps, treatment times can be shortened by over 30% by our SLS plans while maintaining the same treatment quality. We have used SLS in clinical applications at two cancer treatment centers. This paper discusses the various aspects of the implementation, installation, commissioning, and testing of our SLS software system

In this paper, we present a new geometric algorithm for the 3-D static leaf sequencing (SLS) problem arising in intensity-modulated radiation therapy (IMRT), a modern cancer treatment technique. The treatment time and machine delivery error are two crucial factors for measuring the quality of a solution (i.e., a treatment plan) for the SLS problem. In the current clinical practice, physicians prefer to use treatment plans with the lowest possible amount of delivery error, and are also very concerned about the treatment time. Previous SLS methods in both the literature and commercial treatment planning systems either cannot minimize the error or achieve that only by treatment plans which require a prolonged treatment time. In comparison, our new geometric algorithm is computationally efficient; more importantly, it guarantees that the output treatment plans have the lowest possible amount of delivery error, and the treatment time for the plans is significantly shorter. Our solution is based on a number of novel schemes and ideas (e.g., mountain reduction, block matching, profile-preserving cutting, etc) which may be of interest in their own right. Experimental results based on real medical data showed that our new algorithm runs fast and produces much better quality treatment plans than current commercial planning systems and well-known algorithms in medical literature.

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 Steiner points in polynomial time; the previously best known basic 3-D SLS algorithm gives optimal outputs only for the case without 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 and comparisons using real medical data and on a real radiotherapy machine have shown that our 3-D SLS algorithms and software produce treatment plans that use significantly shorter delivery time and give better treatment quality than the current most popular commercial treatment planning system and the most well-known SLS algorithm. Some of our techniques and geometric procedures (e.g., for the problem of partitioning a polygonal domain into a minimum set of x-monotone polygons) are interesting in their own right.