Shape rectangularization problems in intensity-modulated radiation therapy

N. Bansal, D.Z. Chen, D. Coppersmith, X.S. Hu, S. Luan, E. Misiolek, B. Schieber, C. Wang

Research output: Contribution to journalArticleAcademicpeer-review

2 Citations (Scopus)
2 Downloads (Pure)

Abstract

In this paper, we present a theoretical study of several 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¿R, 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(·) is defined on an interval I such that W(x) is a fixed value h>0 for any x¿I and is 0 otherwise. A constant window function can be viewed as a rectangle (or a block) geometrically, or as a vector with the consecutive a’s property combinatorially. The SR problems find applications in setup time and beam-on time minimization and dose simplification of the IMRT treatment planning process. We show that the SR problems are APX-Hard, and thus we aim to develop theoretically efficient and provably good quality approximation SR algorithms. Our main contribution is to present algorithms for a key SR problem that achieve approximation ratios better than 2. For the general case, we give a 24/13-approximation algorithm. For unimodal input curves, we give a 9/7-approximation algorithm. We also consider other variants for which better approximation ratios are possible. We show that an important SR case that has been studied in medical literature can be formulated as a k-MST (k-minimum-spanning-tree) problem on a certain geometric graph G; based on a set of geometric observations and a non-trivial dynamic programming scheme, we are able to compute an optimal k-MST in G efficiently. Keywords: Shape rectangularization – Shape approximation – Integer linear programming – Dynamic programming – Intensity-modulated radiation therapy.
Original languageEnglish
Pages (from-to)421-450
JournalAlgorithmica
Volume60
Issue number2
DOIs
Publication statusPublished - 2011
Externally publishedYes

Fingerprint Dive into the research topics of 'Shape rectangularization problems in intensity-modulated radiation therapy'. Together they form a unique fingerprint.

Cite this