Efficient matching of nonrectangular shapes |
| |
Authors: | Amihood Amir Martin Farach |
| |
Affiliation: | (1) Department of Computer Science and Institute for Advanced Computer Studies, University of Maryland, 20742 College Park, MD, USA;(2) Department of Computer Science, University of Maryland, 20742 College Park, MD, USA |
| |
Abstract: | Most known two-dimensional matching algorithms have a rectangular text (image) and rectangular pattern (template) as their input. These matching algorithms perform a row by row analysis followed by some column processing. These techniques are only efficient if all the rows are of equal length, hence the necessity for rectangular patterns.We present a novel method for analysing patterns with rows of different lengths. This enables finding all occurrences of a nonrectangular figure of heightm in ann×n text in time
. We make use of thesmaller matching problem.The smaller matching problem is that of finding all appearances of a numerical one dimensional pattern in a numerical one-dimensional text, where every element of the pattern is no greater than the corresponding text element.Partially supported by NSF grant CCR-88-03641 and a University of Maryland full year research award.Supported by a University of Maryland Graduate Fellowship, an ACM Samuel M. Alexander Fellowship and NSF grant CCR-88-03641. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|