Menu
Consider a two-dimensional grid (the usual lattice in the plane). For my purposes, a pattern or arrangement is an assignment of the numbers 1 and 2 to some connected subset of the grid points. For example, the following shows three separate arrangements:
.......1.....1....
.222...2.....12...
.111...2.....2....
.222...22...12211.
.......1....11.1..
I say that a small pattern matches a large one if the small one can be rotated or reflected such that all of its numbers are smaller than the numbers in the larger one. For example, consider this pattern:
......
.1212.
....2.
......
It does NOT match the leftmost arrangement above because it can't be rotated or reflected to fit in a 3x3 square. It DOES match the middle arrangement because it can be rotated and reflected to fit underneath. It does NOT, however, match the rightmost arrangement because however it is rotated or reflected to fit in the rightmost arrangement, the numbers are larger in the small pattern than the large arrangement. (If any of my examples are unclear or you need more information, just ask away in the comments area. Some clarifications in advance: the pattern can't be stretched, and it can't be rotated so it's diagonal with respect to the grid. That means there are four rotations and four reflections total, each of which can be translated.)
I am wondering about the following questions:
How can I quickly test if a small pattern matches a large arrangement?
Suppose I have a lot of small patterns. Can I pre-process them somehow to quickly tell if at least one of them matches an arrangement?
I suppose it'd be cool if a solution solves a more general problem (like arbitrary numbers -- not just 1 and 2 -- or allowing disconnected shapes), but I really only care about the case above. Thanks.
481
Pattern-matching algorithms scan the text with the help of a window, whose size is equal to the length of the pattern. The first step is to align the left ends of the window and the text and then compare the corresponding characters of the window and the pattern; this procedure is known as attempt.
The so-called naive or brute force algorithm is the most intuitive approach to the string pattern-matching problem. This algorithm attempts simply to match the pattern in the target at successive positions from left to right.
Like one-dimensional repeating patterns, two-dimensional repeating patterns always have more than one possible unit of repeat. There are usually one or two obvious possibilities, but there are often many others that are less obvious.
The Brute Force algorithm compares the pattern to the text, one character at a time, until unmatching characters are found: - Compared characters are italicized. - Correct matches are in boldface type.
2D convolution.
(complexity is n*Log(n) where n in number of elements) and might be good for larger matrices.
Make both matrices matching and non matching same size.
Test for each number seperatly.
Example - cheking number k
In serchung matrix (bigger) set numbers >= k on 0 other values on 1
In patteren matrix set values <= k on 1 other set on 0
Where the result of convolution is 0 is hit and match
Check for each rotation and reflexion (8 total)
That mean that general comlexity is knlog(n) where k is number of numbers (in your case 2) and n number of elements of bigger matrix)
157
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
