Pruned Continuous Haar Transform of 2D Polygonal Patterns with Application to VLSI Layouts

We introduce an algorithm for the efficient computation of the continuous Haar transform of 2D patterns that can be described by polygons. These patterns are ubiquitous in VLSI processes where they are used to describe design and mask layouts. There, speed is of paramount importance due to the magnitude of the problems to be solved and hence very fast algorithms are needed. We show that by techniques borrowed from computational geometry we are not only able to compute the continuous Haar transform directly, but also to do it quickly. This is achieved by massively pruning the transform tree and thus dramatically decreasing the computational load when the number of vertices is small, as is the case for VLSI layouts. We call this new algorithm the pruned continuous Haar transform. We implement this algorithm and show that for patterns found in VLSI layouts the proposed algorithm was in the worst case as fast as its discrete counterpart and up to 12 times faster.

By: R. Scheibler, P. Hurley, A. Chebira

Published in: Proc. 2010 IRAST Int'l Congress on Computer Applications and Computational Science "CACS 2010," (December 2010), (CD: ISBN:978-981-08-6846-8), International Research Alliance for Science and Technology (IRAST), p.984-987 in 2010

Please obtain a copy of this paper from your local library. IBM cannot distribute this paper externally.

Questions about this service can be mailed to .