论文标题
当Lipschitz散步您的狗时：翻译下离散的Fréchet距离的算法工程
When Lipschitz Walks Your Dog: Algorithm Engineering of the Discrete Fréchet Distance under Translation
论文作者
论文摘要
考虑如何通过在曲线翻译下不变的数量来测量平面中曲线相似性的自然问题。每当我们旨在量化曲线形状的相似性而不是它们在平面中的位置，例如比较手写字符的相似性时，这种度量是合理的。也许最自然的概念是翻译下的（离散的）fréchet距离。不幸的是，有关此问题的算法文献产生了一个非常悲观的观点：在具有$ n $顶点的多边形曲线上，最快的算法在时间$ o（N^{4.667}）上运行，并且不能改善$ N^{4-o（1）} $以下$ o（N^{4.667}）$，除非$ n^{4-o（1）} $否则会达到强大的时间下降。我们仍然可以获得在现实数据集上有效的实现吗？ 由于Fréchet距离的最新实现的令人惊讶的性能，我们对Fréchet距离进行了算法工程。我们的解决方案将连续优化（特别是用于全球Lipschitz优化的分支和结合算法）的快速但不精确的工具与精确但昂贵的算法（根据布置构造）的精确但昂贵的算法（具体，特定于问题的算法）。我们将这两种成分结合在一起，以获得翻译下的Fréchet距离的确切决策算法。对于将距离价值计算至所需精度的相关任务，我们设计并比较不同的方法。在涉及手写字符和路线轨迹的基准集合中，我们的实现回答了几毫秒范围内的任一任务的典型查询，直到标准桌面硬件上的一秒钟。 我们认为，我们的实施将使在应用程序中翻译下的Fréchet距离使用，而以前的方法在计算上是不可行的。
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 $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é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 the use of the Fréchet distance under translation in applications, whereas previous approaches would have been computationally infeasible.
