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

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

2011-05-06

arxiv.org/abs/1105.1261v1

R. Scheibler, P. Hurley, and A. Chebira, "Pruned Continuous Haar Transform of 2D Polygonal Patterns with Application to VLSI L

Computer Science

Computational Engineering, Finance, and Science

4 pages, 5 figures, 1 algorithm

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Pruned Continuous Haar Transform of 2D Polygonal Patterns with Application to VLSI Layouts does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Pruned Continuous Haar Transform of 2D Polygonal Patterns with Application to VLSI Layouts, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Pruned Continuous Haar Transform of 2D Polygonal Patterns with Application to VLSI Layouts will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-576234