Geometric Pattern Match Using Edge Driven Dissected Rectangles and Vector Space.

In this paper, we propose novel algorithms for pattern matching which dissects patterns into rectangles based on polygon edges. Unlike other design rule check (DRC)-based pattern matching algorithms, our solution utilizes simple DRC edge length rules to create rectangles for hotspot pattern descriptions. This approach has at least three advantages over other solutions. First, it is faster than other state-of-the-art pattern matching tools. Second, it is intuitive and simple for pattern matching engineers to understand and describe patterns. Third, it scales well for parallel computation. We also show how to improve pattern matching run time using vector space created by an origin rectangle and other reference rectangles inside a pattern bounding box. By adopting the vector concept, we iterate only once or twice when detecting different pattern orientations. Other pattern matching techniques usually iterate eight times (4 rotations $ \times \,\, 2$ mirrored images) to detect all of the eight different orientations. Our method eliminates these unnecessary iterations. [ABSTRACT FROM PUBLISHER]