Search

In this paper, we study an interesting matrix decomposition problem that seeks to decompose a "complicated" matrix into two "simpler" matrices while minimizing the sum of the horizontal complexity of the first sub-matrix and the vertical complexity of the second sub-matrix. The matrix decomposition problem is crucial for improving the "step-and-shoot" delivery efficiency in Intensity-Modulated Radiation Therapy, which aims to deliver a highly conformal radiation dose to a target tumor while sparing the surrounding normal tissues. Our algorithm is based on a non-trivial graph construction scheme, which enables us to formulate the decomposition problem as computing a minimum s-t cut in a 3-D geometric multi-pillar graph. Experiments on randomly generated intensity map matrices and on clinical data demonstrated the efficacy of our algorithm. [ABSTRACT FROM AUTHOR]

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 using 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. [ABSTRACT FROM AUTHOR]

The 3-D static leaf sequencing (SLS) problem arises in radiation therapy for cancer treatments, aiming to deliver a prescribed radiation dose to a target tumor accurately and efficiently. The treatment time and machine delivery error are two crucial factors to the solution (i.e., a treatment plan) for the SLS problem. In this paper, we prove that the 3-D SLS problem is NP-hard, and present the first ever algorithm for the 3-D SLS problem that can determine a tradeoff between the treatment time and machine delivery error (also called the "tongue-and-groove" error in medical literature). Our new 3-D SLS algorithm with error control gives the users (e.g., physicians) the option of specifying a machine delivery error bound, and subject to the given error bound, the algorithm computes a treatment plan with the minimum treatment time. We formulate the SLS problem with error control as computing a k-weight shortest path in a directed graph and build the graph by computing g-matchings and minimum cost flows. Further, we extend our 3-D SLS algorithm to all the popular radiotherapy machine models with different constraints. In our extensions, we model the SLS problems for some of the radiotherapy systems as computing a minimum g-path cover of a directed acyclic graph. We implemented our new 3-D SLS algorithm suite and conducted an extensive comparison study with commercial planning systems and well-known algorithms in medical literature. Some of our experimental results based on real medical data are presented. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]