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.