Shape rectangularization problems in intensity-modulated radiation therapy

Nikhil Bansal, Danny Z. Chen, Don Coppersmith, Xiaobo S. Hu, Shuang Luan, Ewa Misiołek, Baruch Schieber, Chao Wang

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


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, 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.

Original languageEnglish (US)
Pages (from-to)421-450
Number of pages30
JournalAlgorithmica (New York)
Issue number2
StatePublished - Jun 2011
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • Computer Science Applications
  • Applied Mathematics


  • Dynamic programming
  • Integer linear programming
  • Intensity-modulated radiation therapy
  • Shape approximation
  • Shape rectangularization


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

Cite this