Abstract
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 heightm in ann×n text in time\(O\left( {n^2 \sqrt m \log m} \right)\). We make use of thesmaller 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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
A.V. Aho and M.J. Corasick, Efficient string matching, Comm. ACM 18 (1975) 333–340.
K. Abrahamson, Generalized string matching, SIAM J. Comp. 16 (1987) 1039–1051.
A. Amir, Scaled pattern matching,Proc. 5th Israeli Symp. on AI Vision and Pattern Recognition, Tel-Aviv, Israel (Dec. 1988), pp. 425–440.
A. Amir and G. Landau, Fast parallel and serial multidimensional approximate array matching,Proc. Int. Workshop on Sequences, Combinatorics, Compression, Security and Transmission, Salerno, Italy (June 1988) pp. 3–24.
R.S. Bird, Two dimensional pattern matching, Info. Proc. Lett. 6 (1977) 168–170.
R.S. Boyer and J.S. Moore, A fast string searching algorithm, Comm. ACM 20 (1977) 762–772.
T. Eilam-Tsoreff and U. Vishkih, Matching patterns in a string subject to multilinear transformations,Proc. Int. Workshop on Sequences, Combinatorics, Compression, Security and Transmission, Salerno, Italy (June 1988) pp. 45–57.
M.J. Fischer and M.S. Paterson, String matching and other products, in:Complexity of Computation, R.M. Karp (ed.), SIAM-AMS Proc., vol. 7 (1974) pp. 113–125.
K. Krithivasan and R. Sitalakshmi, Efficient two dimensional pattern matching in the presence of errors, Info. Sci. 13 (1987) 169–184.
S. Rao Kosaraju, Efficient string matching, unpublished manuscript (1987).
D.E. Knuth, J.H. Morris and V.R. Pratt, Fast pattern matching in strings, SIAM J. Comp. 6 (1977) 323–350.
G.M. Landau and U. Vishkin, Efficient string matching in the presence of errors,Proc. 26th IEEE FOCS (1985) pp. 126–136.
G.M. Landau and U. Vishkin, Introducing efficient parallelism into approximate string matching,Proc. 18th ACM Symp. on Theory of Computing (1986) pp. 220–230.
E. Ukkonen, On approximate string matching,Proc. Int. Conf. on Foundations of Computer Theory, Lecture Notes in Computer Science 158 (Springer, 1983) pp. 487–495.
E. Ukkonen, Finding approximate pattern in strings, J. Algorithms 6 (1985) 132–137.
P. Weiner, Linear pattern matching algorithm,Proc. 14th IEEE Symp. on Switching and Automata Theory (1973) pp. 1–11.
Author information
Authors and Affiliations
Additional information
Partially supported by NSF grant CCR-88-03641 and a University of Maryland full year research award.
Supported by a University of Maryland Graduate Fellowship, an ACM Samuel M. Alexander Fellowship and NSF grant CCR-88-03641.
Rights and permissions
About this article
Cite this article
Amir, A., Farach, M. Efficient matching of nonrectangular shapes. Ann Math Artif Intell 4, 211–224 (1991). https://doi.org/10.1007/BF01531057
Issue date:
DOI: https://doi.org/10.1007/BF01531057