文章基本信息

标题：When Lipschitz Walks Your Dog: Algorithm Engineering of the Discrete FrÃ©chet Distance Under Translation
本地全文：下载
作者：Karl Bringmann ; Marvin K{"u}nnemann ; Andr Nusser 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：173
页码：25:1-25:17
DOI：10.4230/LIPIcs.ESA.2020.25
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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Ã©chet 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 ð'ª(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Ã©chet distance, we perform algorithm engineering for the FrÃ©chet 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Ã©chet 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, for the first time, the use of the FrÃ©chet distance under translation in applications, whereas previous algorithmic approaches would have been computationally infeasible. Furthermore, we hope that our combination of continuous optimization and computational geometry will inspire similar approaches for further algorithmic questions.
关键词：FrÃ©chet Distance; Computational Geometry; Continuous Optimization; Algorithm Engineering