CLR cover

Problem 44: Searching Irregular 2D Patterns

Let $P$ be a given (potentially) irregular two-dimensional (2D) pattern. By irregular is meant that $P$ is not necessarily a rectangle, it can be of any shape. The aim is to find all occurrences of $P$ in a 2D $n\times n'$ text $T$ of total size $N=n n'$.

Show that two-dimensional pattern matching of irregular 2D-patterns can be done in $O( N\log N) $ time.

References

  • A. Amir and M. Farach. Efficient matching of nonrectangular shapes. Ann. Math. Artif. Intell., 4:211-224, 1991.