Faster two-dimensional pattern matching with rotations

The most efficient currently known algorithms for two-dimensional pattern matching with rotations have a worst case time complexity of O ( n 2 m 3 ), where the size of the text is n × n and the size of the pattern is m × m. In this paper we present a new algorithm for the problem whose running time is O ( n 2 m 2 ).

Authors

• Amihood Amir
• Oren Kapah
• Dekel Tsur

Keywords

• Design and analysis of algorithms
• Two-dimensional pattern matching
• Rotation