Fr\'echet Distance Revisited and Extended
Fr\'echet Distance Revisited and Extended
复制标题
Frechet距离的重新审视和扩展
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Benjamin Raichel
中科院分区：
文献类型：
--
作者：
Sariel Har;Benjamin Raichel
给定在r^d中的两个简单复合物，并在每个复合物中的启动和末端顶点，我们展示了如何在这些顶点之间计算曲线（在每个复合物中），从而使这些曲线之间的fr \'echet距离最小化。由于多边形曲线是一个复杂的曲线，因此这概括了曲线之间弱的Fr \'echet距离的常规概念。我们还概括了算法以处理k简单复合物的输入。
使用这种新算法，我们可以解决许多新问题，从计算给定曲线集合的平均曲线到各种运动计划问题。此外，我们表明，对于平均曲线问题，当k输入曲线被c包装时，对于固定的k和epsilon，可以（1+epsilon）在几乎线性时间内平均曲线。
此外，我们提出了一种用于计算两条曲线之间强fr \'echet距离的算法，这比以前的算法更简单，并避免使用参数搜索。
Given two simplicial complexes in R^d, and start and end vertices in each complex, we show how to compute curves (in each complex) between these vertices, such that the Fr\'echet distance between these curves is minimized. As a polygonal curve is a complex, this generalizes the regular notion of weak Fr\'echet distance between curves. We also generalize the algorithm to handle an input of k simplicial complexes.
Using this new algorithm we can solve a slew of new problems, from computing a mean curve for a given collection of curves, to various motion planning problems. Additionally, we show that for the mean curve problem, when the k input curves are c-packed, one can (1+epsilon)-approximate the mean curve in near linear time, for fixed k and epsilon.
Additionally, we present an algorithm for computing the strong Fr\'echet distance between two curves, which is simpler than previous algorithms, and avoids using parametric search.