Two-dimensional pattern matching by sampling

Maxime Crochemore, Leszek Ga̧sieniec, Wojciech Rytter

Research output: Contribution to journalArticlepeer-review

4 Scopus citations


We extend the concept of deterministic sampling to the two-dimensional pattern matching problem. We show that almost all patterns have a logarithmic deterministic sample. There are 2D-matching algorithms which work efficiently for almost all patterns. They solve the 2D-matching problem in linear sequential time with 0(1) space, or, alternatively in 0(1) parallel time with linear number of processors. This is the first attempt to reduce the space for two-dimensional pattern matching.

Original languageEnglish (US)
Pages (from-to)159-162
Number of pages4
JournalInformation Processing Letters
Issue number4
StatePublished - Jun 25 1993
Externally publishedYes


  • Analysis of algorithms

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications


Dive into the research topics of 'Two-dimensional pattern matching by sampling'. Together they form a unique fingerprint.

Cite this