Algorithms for the Computation of Continuous Transforms of Rectilinear Polygons from IC Layouts

In this work, we present a novel way of computing the continuous Haar, Fourier and cosine series coefficients of rectilinear polygons. We derive algorithms to compute the inner products with the continuous basis functions directly from the vertices of the polygons. We show that the overall computational complexity of those algorithms is lower than that of the traditional corresponding discrete transforms when the number of vertices is small, in addition to sparing the memory needed for a discrete image. This makes those continuous transforms particularly suitable for applications in Computational Lithography (CL) where speed and memory are critical requirements. We validate the presented algorithms through an implementation in a CL software under development at the IBM Zurich Research Laboratory and benchmark against discrete state of the art transforms on real Integrated Circuit (IC) layouts. Finally, we measure the approximation power of the Haar transform when applied to rectilinear polygons from IC layouts in order to evaluate its potential for pattern matching applications.