Characterization of a next generation step-and-scan system
Timothy J. Wiltshire, Joseph P. Kirk, et al.
SPIE Advanced Lithography 1998
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. © 2009 Springer Science+Business Media, LLC.
Timothy J. Wiltshire, Joseph P. Kirk, et al.
SPIE Advanced Lithography 1998
Frank R. Libsch, Takatoshi Tsujimura
Active Matrix Liquid Crystal Displays Technology and Applications 1997
Donald Samuels, Ian Stobert
SPIE Photomask Technology + EUV Lithography 2007
John R. Kender, Rick Kjeldsen
IEEE Transactions on Pattern Analysis and Machine Intelligence