Personal tools
You are here: Home CG seminar 2018 Algorithms for the discrete Frechet distance under translation
« December 2018 »
December
SuMoTuWeThFrSa
1
2345678
9101112131415
16171819202122
23242526272829
3031
Log in


Forgot your password?
 

Algorithms for the discrete Frechet distance under translation

Wednesday, December 27th, 2017, 16:10

Schreiber 309

underline

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.

Document Actions