This work deals with the dummy fill and negative fill insertion problem with constraints on the minimum and maximum pattern density within a moving rectangular window. It is shown in the paper that the general class of such problems defined with a gridless formulation is at least NP-hard. Our conjecture is that the problem is at least NP-hard in the gridded domain as well. A greedy randomized algorithm for one of our problems in the gridded domain is proposed, together with proof of convergence and some experimental results. More detailed account of our implementation and results are available in [1].
Index Terms - Fill, negative fill, Design for Manufacturing (DFM), NP-Hard, Randomization