Speaker: Rinat Ben Avraham

Title: Geometric pattern matching algorithms

Abstract:
---------
We study several problems in shape matching, concentrating on geometric
pattern matching of sequences of points.

The main approach is to measure the similarity between two point sequences
using the discrete Fr\'echet distance. Roughly, the discrete Fr\'echet
distance between a point sequence P and a point sequence Q is defined as
the minimum, over all possible independent (forward) traversals of the
sequences, of the maximum distance between the current point of P and the
current point of Q during the traversals.

This useful measure has applications in many fields of computer science
such as computer vision, pattern recognition and computational biology.

Applications include comparing silhouette curves in an image, matching a
path in a map to GPS tracking data, measuring the similarity of the folded
structures of biomolecules such as proteins, and more.

In this talk I will present several algorithms for computing variants of
the discrete Fr\'echet distance.

(i) The first subquadratic algorithm for computing the discrete Fr\'echet
distance itself,

(ii) Algorithms for computing the discrete Fr\'echet distance where the
sequences of points may contain noise (outliers) that we wish to ignore by
allowing shorcuts to be made in one or both sequences, and

(iii) An algorithm for computing the minimum Fr\'echet distance under
translation of the point-sequences.

Joint work with Haim Kaplan and Micha Sharir, and in part also with Pankaj
Agarwal, Omrit Filtser, and Matthew Katz.