caa a22 4500 445804688 CHVBK 20180317145153.0 cr unu---uuuuu 170323e20110601xx s 000 0 eng 10.1007/s00453-009-9354-8 doi (NATIONALLICENCE)springer-10.1007/s00453-009-9354-8 Shape Rectangularization Problems inIntensity-Modulated Radiation Therapy [Elektronische Daten] [Nikhil Bansal, Danny Chen, Don Coppersmith, Xiaobo Hu, Shuang Luan, Ewa Misiołek, Baruch Schieber, Chao Wang] 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. Aconstant 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. Aconstant window function can be viewed as a rectangle (or ablock) 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 than2. For the general case, we give a $\frac{24}{13}$-approximation algorithm. For unimodal input curves, we give a $\frac{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. Springer Science+Business Media, LLC, 2009 Shape rectangularization nationallicence Shape approximation nationallicence Integer linear programming nationallicence Dynamic programming nationallicence Intensity-modulated radiation therapy nationallicence Bansal Nikhil IBM T.J. Watson Research Center, P.O. Box 218, 10598, Yorktown Heights, NY, USA aut Chen Danny Department of Computer Science and Engineering, University of Notre Dame, 46556, Notre Dame, IN, USA aut Coppersmith Don IDA Center for Communications Research, 805 Bunn Drive, 08540, Princeton, NJ, USA aut Hu Xiaobo Department of Computer Science and Engineering, University of Notre Dame, 46556, Notre Dame, IN, USA aut Luan Shuang Department of Computer Science, University of New Mexico, 87131-0001, Albuquerque, NM, USA aut Misiołek Ewa Mathematics Department, Saint Mary's College, 46556, Notre Dame, IN, USA aut Schieber Baruch IBM T.J. Watson Research Center, P.O. Box 218, 10598, Yorktown Heights, NY, USA aut Wang Chao Department of Computer Science and Engineering, University of Notre Dame, 46556, Notre Dame, IN, USA aut Algorithmica Springer-Verlag 60/2(2011-06-01), 421-450 0178-4617 60:2<421 2011 60 453 https://doi.org/10.1007/s00453-009-9354-8 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-009-9354-8 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Bansal Nikhil IBM T.J. Watson Research Center, P.O. Box 218, 10598, Yorktown Heights, NY, USA aut NATIONALLICENCE 700 1- Chen Danny Department of Computer Science and Engineering, University of Notre Dame, 46556, Notre Dame, IN, USA aut NATIONALLICENCE 700 1- Coppersmith Don IDA Center for Communications Research, 805 Bunn Drive, 08540, Princeton, NJ, USA aut NATIONALLICENCE 700 1- Hu Xiaobo Department of Computer Science and Engineering, University of Notre Dame, 46556, Notre Dame, IN, USA aut NATIONALLICENCE 700 1- Luan Shuang Department of Computer Science, University of New Mexico, 87131-0001, Albuquerque, NM, USA aut NATIONALLICENCE 700 1- Misiołek Ewa Mathematics Department, Saint Mary's College, 46556, Notre Dame, IN, USA aut NATIONALLICENCE 700 1- Schieber Baruch IBM T.J. Watson Research Center, P.O. Box 218, 10598, Yorktown Heights, NY, USA aut NATIONALLICENCE 700 1- Wang Chao Department of Computer Science and Engineering, University of Notre Dame, 46556, Notre Dame, IN, USA aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 60/2(2011-06-01), 421-450 0178-4617 60:2<421 2011 60 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer