We give an algorithm for two-dimensional pattern matching in the presence of errors. We find that the complexity of our algorithm is O(kn1n2 log n2 + n12n2 + kn1m1m2), where the pattern is an n1 × n2 array, the text is an m1 × m2 array and k is the number of mismatches allowed. © 1987.

Kamala Krithivasan

Computer Programming - Algorithms

Computational complexity

MATCHING ERRORS

Object Recognition

TWO-DIMENSIONAL PATTERN MATCHING

Pattern Recognition

IIT Madras is a public technical and research university located in Chennai, Tamil Nadu. Founded in 1959, it is recognised as an Institute of National Importance.

IIT Madras has been ranked as the top engineering institute in India for four years in a row by the National Institutional Ranking Framework of the MHRD

It currently offers undergraduate, postgraduate and research degrees across 16 disciplines in Engineering, Sciences, Humanities and Management. About 596 faculty belonging to science and engineering departments and centres of the Institute are engaged in teaching, research and industrial consultancy.

IIT Madras

Efficient two-dimensional pattern matching in the presence of errors

Information Sciences

Proceedings of the eighteenth annual ACM symposium on Theory of computing - STOC '86

Introducing efficient parallelism into approximate string matching and a new serial algorithm

Theoretical Computer Science

Efficient string matching with k mismatches

26th Annual Symposium on Foundations of Computer Science (sfcs 1985)

Efficient string matching in the presence of errors

Information Processing Letters

Two dimensional pattern matching

Journal	Information Sciences
ISSN	00200255
Open Access	No