OPTIMUM SCAN-WIDTH SELECTION UNDER CONTAINMENT CONSTRAINTS

作     者：GAREY, MR PINTER, RY 

作者机构：AT&T Bell Laboratories. Michael R. Garey: B.S. (Mathematics) 1967 M.S. (Computer Science) 1969 and Ph.D. (Computer Science) 1970 University of Wisconsin AT&T Bell Laboratories 1970—. Ron Y. Pinter: B.S. (Computer Science) 1975 Technion—Israel Institute of Technology S.M. and Ph.D. (Computer Science) The Massachusetts Institute of Technology 1980 and 1982 respectively AT&T Bell Laboratories 1982–1983 IBM Israel Scientific Center 1983—. 

出 版 物：《AT&T BELL LABORATORIES TECHNICAL JOURNAL》 (Bell Labs Tech J)

年 卷 期：1984年第63卷第6期

页      面：1191-1212页

核心收录：

学科分类：0810[工学-信息与通信工程] 0809[工学-电子科学与技术（可授工学、理学学位）] 08[工学] 

摘      要：We consider the following algorithmic problem, which arises in connection with optimally choosing beam widths and positions for electron exposure of integrated circuit wafers. Let H 0 be a fixed real number, and let c be a fixed, positive-valued, nondecreasing cost function defined on (0, H ]. An instance of the problem consists of a given range R = [ a, b ] and n given intervals I i = [ a i , b i ], 1 ≤ i ≤ n , each contained in R and of length not exceeding H . A solution (or feasible solution) for such an instance is a collection of segments, S 1 , S 2 , …, S k , each of length at most H and contained in R , such that each given interval is contained in at least one segment and the union of all the segments is R . The goal is to find an optimal solution with respect to c , i.e., a solution for which the sum of the costs of the individual segment lengths is as small as possible. The segments in a solution describe the beam positions and widths, projected on one side of the wafer, and the given intervals correspond to particularly sensitive regions on the layout mask, each of which must be entirely exposed by a single scan. The cost function gives the time required for a single scan of given width, including alignment overhead. Using dynamic programming techniques, we give efficient algorithms and data structures for solving this problem for several natural classes of cost functions, the most general of which is the class of all concave increasing functions, solved by an algorithm that runs in time O ( n 2 ).