Efficient matching of nonrectangular shapes

Amihood Amir, Martin Farach

Research output: Contribution to journalArticlepeer-review

4 Scopus citations


Most known two-dimensional matching algorithms have a rectangular text (image) and rectangular pattern (template) as their input. These matching algorithms perform a row by row analysis followed by some column processing. These techniques are only efficient if all the rows are of equal length, hence the necessity for rectangular patterns. We present a novel method for analysing patterns with rows of different lengths. This enables finding all occurrences of a nonrectangular figure of height m in an n×n text in time {Mathematical expression}. We make use of the smaller matching problem. The smaller matching problem is that of finding all appearances of a numerical one dimensional pattern in a numerical one-dimensional text, where every element of the pattern is no greater than the corresponding text element.

Original languageEnglish (US)
Pages (from-to)211-224
Number of pages14
JournalAnnals of Mathematics and Artificial Intelligence
Issue number3-4
StatePublished - Sep 1991
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Artificial Intelligence
  • Applied Mathematics


Dive into the research topics of 'Efficient matching of nonrectangular shapes'. Together they form a unique fingerprint.

Cite this