hide
Free keywords:
Computer Science, Computational Geometry, cs.CG,Computer Science, Data Structures and Algorithms, cs.DS
Abstract:
Consider the natural question of how to measure the similarity of curves in
the plane by a quantity that is invariant under translations of the curves.
Such a measure is justified whenever we aim to quantify the similarity of the
curves' shapes rather than their positioning in the plane, e.g., to compare the
similarity of handwritten characters. Perhaps the most natural such notion is
the (discrete) Fr\'echet distance under translation. Unfortunately, the
algorithmic literature on this problem yields a very pessimistic view: On
polygonal curves with $n$ vertices, the fastest algorithm runs in time
$O(n^{4.667})$ and cannot be improved below $n^{4-o(1)}$ unless the Strong
Exponential Time Hypothesis fails. Can we still obtain an implementation that
is efficient on realistic datasets?
Spurred by the surprising performance of recent implementations for the
Fr\'echet distance, we perform algorithm engineering for the Fr\'echet distance
under translation. Our solution combines fast, but inexact tools from
continuous optimization (specifically, branch-and-bound algorithms for global
Lipschitz optimization) with exact, but expensive algorithms from computational
geometry (specifically, problem-specific algorithms based on an arrangement
construction). We combine these two ingredients to obtain an exact decision
algorithm for the Fr\'echet distance under translation. For the related task of
computing the distance value up to a desired precision, we engineer and compare
different methods. On a benchmark set involving handwritten characters and
route trajectories, our implementation answers a typical query for either task
in the range of a few milliseconds up to a second on standard desktop hardware.
We believe that our implementation will enable the use of the Fr\'echet
distance under translation in applications, whereas previous approaches would
have been computationally infeasible.
