## Abstract

Given two sets of points, the text and the pattern, determining whether the pattern "appears" in the text is modeled as the point set pattern matching problem. Applications usually ask for not only exact matches between these two sets, but also approximate matches. In this paper, we investigate a one-dimensional approximate point set pattern matching problem proposed in [19]. We generalize the measure between approximate matches from ^{L1}-norm to L_{p}-norm. More specifically, what requested is an optimal match which minimizes the L_{p}-norm of the difference vector (| ^{p2}-^{p1}-(t2′-t1′)|,|^{p3}- ^{p2}-(t3′-t2′)|,.,|P_{m}-pm-_{1}- (tm′-tm-1′)|), where ^{p1},^{p2},.,P_{m} is the pattern and t1′,t2′,.,tm′ is a subsequence of the text. For p→∞, we propose an O(mn)-time algorithm, where m and n denote the lengths of the pattern and the text, respectively. For arbitrary p<∞, we propose an algorithm which runs in O(mnT(p)) time, where T(p) is the time of evaluating x^{p} for xεR.

Original language | English |
---|---|

Pages (from-to) | 42-50 |

Number of pages | 9 |

Journal | Theoretical Computer Science |

Volume | 521 |

DOIs | |

Publication status | Published - 2014 Feb 13 |

Externally published | Yes |

## Keywords

- Dynamic programming
- L-norm
- Point set pattern matching

## ASJC Scopus subject areas

- Theoretical Computer Science
- Computer Science(all)

## Fingerprint

Dive into the research topics of 'One-dimensional approximate point set pattern matching with L_{p}-norm'. Together they form a unique fingerprint.