Supplemental Information for M3: Maskless Microscope-Based Micropatterning with Dry Film

Leigh et al.1

Supplemental Information for M3: Maskless Microscope-based Micropatterning with Dry Film Photoresist

Part II: Algorithm for generation of arbitrary patterns

We show that is possible tocreate disconnected patterns in the Ordyl SY330 DFP without a need for shuttering the light. Although the methodinvolves continuous exposure of the DFP, the principle of exposure superposition is used in conjunction with “Traveling Salesman”tour construction1 and improvements heuristics2 in order to plan a path of exposure that ensures suprathreshold UV dosage occurs only at the desired locations.

Path planning for exact double-exposure of a point set

Continuous light exposure and uninterrupted pattern writing, described in the manuscript, presents a problem when disconnected patterns need to be generated. We have developed a general algorithm to address such cases. When the UV dose at a given point in the plane of the DFP is between 50% and 100% of the dose needed to produce a feature, the superposition of two exposures is now necessary to produce a feature. Taking advantage of this material property of the DFP, we propose a method for double-exposing desired points in the DFPin such a way that the points produced match the input set of points exactly (i.e., there are no missing or extra points). A general solution is proposed below:

Problem: Given a finite set Sof n points (or, more generally, of ndisjoint line segments) in the plane, find a path P in the plane so that S is exactly equal to the set of points that are (exactly) double-covered by P.
Solution: If S is a finite set of n points in the plane, then such a path P always exists and can be computed efficiently by the following method. First, compute a path P’ that is a simple polygonalization of the set S; i.e., P’ is a simple (non-self-intersecting) polygonal path whose vertices are exactly the n points S. Such a polygonalization P’ can be found easily in time O(n log n), e.g., by sorting the points S by x-coordinates, breaking ties according to y-coordinates; the resulting x-monotone polygonal path, P’, can then be modified locally, at each of its vertices, so that the modified path, P, has the desired property. Specifically, for each (internal) vertex v of P’ we extend the two edges incident to v slightly, by a small length , and then join the extension endpoints with a short segment (of length at most 2), resulting in a small isosceles triangle with apex at v. The modified path enters v, passing through it and going beyond v by distance , then traverses the short edge opposite v, and then passes back through v along the extension of the edge exiting v in path P’. As a result of this local modification of P’ at each (internal) vertex v, each point v  S is exactly double-covered by P. A similar approach applies to the case in which S is a set of disjoint line segments; however, the initial polygonalization P’ of S may have (“Steiner”) vertices that are not part of the set of endpoints of the input set S, since a polygonalization without such additional points may not exist.

While the x-sorted polygonal path, P’, through S yields a simple (non-self-intersecting) path, as is needed for the claim that the modified path P double-covers exactly the set S, such a path may not be desirable in practice because it may be quite long or may have many sharp turns. A potentially better approach to obtain P is to begin with a path P’ that approximates the Traveling Salesman Problem (TSP) path, which is a shortest path visiting the set S of input points. Common approaches to computing an approximating TSP path include the use of construction1 and improvement2 heuristics, nearest-neighbor insertion, doubling the minimum spanning tree, nearest insertion, cheapest insertion, and the Christofides heuristic; see, e.g., Lawler et al.3. While some of these heuristics (e.g., nearest-neighbor) are not guaranteed to produce a simple path/tour, we can postprocess any path/tour using an improvement heuristic, such as 2-opt,2 which guarantees that all crossings in the primary tour will be removed4, implying that no extra features will appear after the DFP has been fully processed. (It is a straightforward consequence of the triangle inequality that a shortest TSP path/tour must be simple; however, heuristics for approximating the NP-hard TSP can result in a non-simple path or tour.) From such a polygonalization P’ of the points, we apply the local tour modification described above to obtain the desired path P having a small triangular loop in the vicinity of each vertex v of P’.

This algorithm extends the versatility and applicability of the maskless photolithographic technique, allowing it to realize patterns that contain connected components, disconnected components, or both (Table 1). The details of optimality relating to our approach, such as execution time, robustness and tour length can be found in Bentley1, Lawler et al.3, and Rosenkrantz et al.5

Table 1

*ET is the exposure threshold that induces feature creation in the photoresist

REFERENCES

1.J. J. Bentley, INFORMS Journal on Computing, 1992, 4, 387.

2.S. Lin and B. W. Kernighan, Operations Research, 1973, 498-516.

3.E. L. Lawler, J. K. Lenstra, A. Kan, and D. B. Shmoys, The traveling salesman problem: a guided tour of combinatorial optimization, Wiley New York, 1985.

4.M. M. Flood, Operations Research, 1956, 61-75.

5.D. J. Rosenkrantz, R. E. Stearns, and P. M. Lewis II, SIAM J. Comput., 1977, 6, 563-581.

6.M. De Berg, O. Cheong, M. Van Kreveld, and M. Overmars, Computational geometry: algorithms and applications, Springer-Verlag New York Inc, 2008.

7.M. Fleury, Journal de mathematiques elementaires, 1883, 257–261.