Shape Rectangularization Problems in Intensity-Modulated Radiation Therapy

In this paper, we present a theoretical study of several geometric shape approximation problems, called shape rectangularization (SR), which arise in intensity-modulated radiation therapy (IMRT). Given a piecewise linear function f such that f(x) ≥0 for any x∈ℝ, the SR problems seek an optimal set of constant window functions to approximate f under a certain error criterion, such that the sum of the resulting constant window functions equals (or well approximates) f. A constant window function W( Open image in new window ) is defined on an interval I such that W(x) is a fixed value h>0 for any x ∈I and is 0 otherwise. Geometrically, a constant window function can be viewed as a rectangle (or a block). The SR problems find applications in micro-MLC scheduling and dose calculation of the IMRT treatment planning process, and are closely related to some well studied geometric problems. The SR problems are NP-hard, and thus we aim to develop theoretically efficient and provably good quality approximation SR algorithms. Our main results include a polynomial time \((\frac{3}{2}+\epsilon)\)-approximation algorithm for a general key SR problem and an efficient dynamic programming algorithm for an important SR case that has been studied in medical literature. Our key ideas include the following. (1) We show that a crucial subproblem of the key SR problem can be reduced to the multicommodity demand flow (MDF) problem on a path graph (which has a known (2+ε)-approximation algorithm); further, by extending the result of the known (2+ε)-approximation MDF algorithm, we develop a polynomial time \((\frac{3}{2}+\epsilon)\)-approximation algorithm for our first target SR problem. (2) We show that the second target SR problem can be formulated as a k-MST problem on a certain geometric graph G; based on a set of interesting geometric observations and a non-trivial dynamic programming scheme, we are able to compute an optimal k-MST in G efficiently.