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.

Kannan and Warnow [Triangulating Three-Colored Graphs, Proc. 2nd SODA, 1991, pp. 337–343 and SIAM J. Discrete Math., 5 (1992), pp. 249–258] describe an algorithm to decide whether a three-colored graph can be triangulated so that all the edges connect vertices of different colors. This problem is motivated by a problem in evolutionary biology. Kannan and Warnow have two implementation strategies for their algorithm: one uses slightly superlinear time, while the other uses linear time but quadratic space. We note that three-colored triangulatable graphs are always planar, and we use this fact to modify Kannan and Warnow’s algorithm to obtain an algorithm that uses both linear time and linear space.