Pattern matching is a key technique in the physical verification of integrated circuit designs and is widely used in lithographic hotspot detection. Existing pattern-matching algorithms face challenges in effectiveness and robustness, especially when processing complex patterns. We propose a pattern-matching algorithm based on augmented vertex hashing that correctly handles polygons with holes and supports fuzzy matching. For exact matching, our method encodes Manhattan polygons into fixed-length hash values using the augmented vertex representation, enabling fast polygon comparisons. For fuzzy matching, we formulate the problem as a constellation problem over augmented vertices and solve it efficiently using a cache-friendly algorithm based on a Bloom filter. Experiments show that our approach is more than 5× faster than the current state of the art on average.
Niu et al. (Thu,) studied this question.