# Algorithms for the discrete Frechet distance under translation

### Wednesday, December 27th, 2017, 16:10

### Schreiber 309

### Algorithms for the discrete Frechet distance under translation

### Omrit Filtser, BGU

### Abstract:

The (discrete) Frechet distance is a popular similarity measure for curves. Often the input curves are not aligned, so one of them must undergo some transformation for the distance computation to be meaningful. Ben Avraham et al. presented an O(m^3n^2(1+log(n/m))log(m+n))-time algorithm for the discrete Frechet distance between two sequences of points of sizes m and n in the plane under translation. In this talk we consider two variants of the discrete Frechet distance: the discrete Frechet distance with shortcuts and the weak discrete Frechet distance, both under translation.

For the discrete Frechet distance with shortcuts in the plane, we present an O(m^2n^2 log^2(m+n))-time algorithm, by presenting a data structure, based on Sleator and Tarjan's Link-Cut Trees, for dynamic maintenance of reachability in the underlying directed graph.

In 1D, we show how to avoid the use of parametric search and remove a logarithmic factor from the running times of (the 1D versions of) these algorithms and of an algorithm for the weak discrete Frechet distance.

Our 1D algorithms follow a general scheme introduced by Martello et al. for the Balanced Optimization Problem (BOP), which is especially useful when an efficient dynamic version of the feasibility decider is available. We present an alternative scheme for BOP, whose advantage is that it yields efficient algorithms quite easily, without having to devise a specially tailored dynamic version of the feasibility decider. We demonstrate our scheme on the *most uniform path* problem, and observe that the weak discrete Frechet distance under translation in 1D is a special case of it.