In this paper, a class of problems of physical-design optimization with rectangular shapes is presented. Efficient solutions for this class of optimization problems are needed for rectangular metal fill/negative-fill insertion during postrouting optimization. These problems are also shown to be closely related to the problem of floorplanning with rectangular macrocells. The solution must satisfy certain constraints for minimum and maximum pattern densities within a moving rectangular window while optimizing a given objective function such as the area or the aspect ratio of the resultant bounding box. It is shown in this paper that the general class of such problems defined with a gridless formulation is at least NP-hard. This proof, with minor modifications, also extends to the formulation in the gridded domain. A greedy randomized algorithm for one of our problems in the gridded domain is proposed, along with a proof that this algorithm can achieve the given objective with a very high probability while satisfying the constraints. Experimental results based on an implementation of our algorithm are provided and are shown to agree with our theoretical proof.

The continuous drive of very large scale integrated (VLSI) chip manufacturers to meet Moore's law has spurred the development of novel resolution enhancement techniques (RETs) and optical proximity correction (OPC) methodologies in optical microlithography. These RET and OPC methods have increased the complexity of mask-manufacturing manifold and have, at the same time, put added emphasis on the mask inspection procedure. A technique to simplify mask inspection is to identify rectangular regions on the mask that do not require inspection. Such a region is referred to as a do not inspect region (DNIR). A novel and practical algorithm to place DNIR rectangles on the mask is presented. It is shown that the most general DNIR placement problem is at least NP-Hard (Garey and Johnson, 1979). However, under certain relaxed criteria, there exists a polynomial-time algorithm for DNIR placement using dynamic programming. However, the optimal algorithm has very-high-degree polynomial bounds on its runtime and space complexities. On the other hand, a very simple greedy algorithm extended by lookahead and randomization, or by simulated annealing, can greatly improve the performance of the DNIR placement and produce near-optimal results. Although the algorithm developed in this work is targeted primarily toward DNIR placement, it has many other VLSI design applications.

XYZ-tree is a hybrid data structure between object space and volume enumeration representation schemes. It is useful for isothetic polygons/polyhedrons and rectangles/rectangular parallelopipeds in 2/3-d. It is a compact and efficient data structure for representing city scape, VLSI circuits, printed circuit boards, etc. Trees may be combined using Boolean operators.