MULTIPLE MATCHING OF RECTANGULAR PATTERNS

We describe the first worst-case efficient algorithm for simultaneousl y matching multiple rectangular patterns of varying sizes and aspect r atios in a rectangular text. Efficient means significantly more effici ent asymptotically than applying known algorithms that handle one heig ht (or width or aspect ratio) at a time for each height. Our algorithm features an interesting use of multidimensional range searching, as w ell as new adaptations of several known techniques for two-dimensional string matching. We also extend our algorithm to a dynamic setting wh ere the set of patterns can change over time. (C) 1995 Academic Press, Inc.