title: Fast two-dimensional pattern matching
body: <p>Consider a two-dimensional grid (the usual lattice in the plane).  For my purposes, a <em>pattern</em> or <em>arrangement</em> 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:</p>
  
  <pre><code>.......1.....1....
  .222...2.....12...
  .111...2.....2....
  .222...22...12211.
  .......1....11.1..
  </code></pre>
  
  <p>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:</p>
  
  <pre><code>......
  .1212.
  ....2.
  ......
  </code></pre>
  
  <p>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.)</p>
  
  <p>I am wondering about the following questions:</p>
  
  <ol>
  <li><p>How can I quickly test if a small pattern matches a large arrangement?</p></li>
  <li><p>Suppose I have a lot of small patterns.  Can I pre-process them somehow to quickly tell if <em>at least one</em> of them matches an arrangement?</p></li>
  </ol>
  
  <p>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.</p>