Multiple matching of rectangular patterns
Ramana M. Idury, Alejandro A. Schäffer · 1993
We describe the first .efiicientalgorithm for simultaneously matching multiple rectangular patterns of varying sizes and aspect, ratios in a rectangular text.Efficient means significantly better asymptotically than known al,qorithrns that handle one height, width, or aspect ratio at a time.Our algorithm features an interesting use of multidimensional range searching, as well as new adaptations of several known techniques for two climensional string matching.We also extend our algorithm to a dynamic setting where the set of patterns can change over time. 1 Machinery.