Patent ID: 8151236

Claim:
A method for mask data preparation, for use with a preliminary mask layout that includes a starting polygon, the starting polygon consisting of a plurality of boundary segments connecting pairs of starting polygon vertices, the starting polygon having an interior, wherein the vertices of the starting polygon include at least one I-point each having an interior angle strictly greater than 90 degrees, the method comprising: by a computer system, constructing a spanning tree connecting all the I-points of the starting polygon as well as all the R-points of the starting polygon, the R-points being all boundary of the starting polygon which do not coincide with a vertex, and which are disposed rectilinearly across the starting polygon interior from one of the I-points; traversing the spanning tree recursively according to the tree structure; in dependence upon the step of traversing, developing a rectilinear partition tree having a plurality of nodes and a plurality of edges connecting pairs of the nodes, the plurality of nodes including all I-points of the starting polygon, the plurality of edges including at least one connected to each of the I-points; and outputting a plurality of sub-polygons which collectively partition the starting polygon, all the sides of all of the sub-polygons lying on either a boundary of the starting polygon or an edge of the partition tree or both.