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.

Published in:
Proceedings of the 2010 IRAST International Congress on Computer Applications and Computational Science, 984–987
Presented at:
International Congress on Computer Applications and Computational Science, Singapour, December 2010

 Record created 2013-05-27, last modified 2018-03-17

Publisher's version:
Download fulltext

Rate this document:

Rate this document:
(Not yet reviewed)