Two-Dimensional Scaled Pattern Matching

Years and Authors of Summarized Original Work

• 2006; Amir, Chencinski

Problem Definition

Definition 1

Let T be a two-dimensional ${ n \times n }$ array over some alphabet Σ.

• 1. The unit pixels array for T (T^1X) consists of n² unit squares, called pixels in the real plane ${ \Re^2 }$. The corners of the pixel ${ T[i,j] }$ are $(i-1,j-1), (i, j-1), (i-1,j),$ and ${ (i,j) }$. Hence the pixels of T form a regular ${ n \times n }$ array that covers the area between ${ (0,0), (n,0), (0,n), }$ and ${ (n,n) }$. Point ${ (0,0) }$ is the origin of the unit pixel array. The center of each pixel is the geometric center point of its square location. Each pixel ${ T[i,j] }$ is identified with the value from Σ that the original array T had in that position. Say that the pixel has a color or a character from Σ. See Fig. 1 for an example of the grid and pixel centers of a ${ 7 \times 7 }$ array.

  Figure 1

  

  The grid and pixel centers of a unit pixel array for a \(...