Computing the Fréchet Distance with a Retractable Leash
Computing the Fréchet Distance with a Retractable Leash
复制标题
使用可伸缩皮带计算 Fréchet 距离
DOI：
10.1007/s00454-016-9800-8
复制
发表时间：
2016
影响因子：
0.8
通讯作者：
Wolfgang Mulzer
中科院分区：
文献类型：
--
作者：
Kevin Buchin;Maike Buchin;Rolf van Leusden;Wouter Meulemans;Wolfgang Mulzer
所有已知的曲线间 Fréchet 距离算法都分两步进行：首先，它们为决策版本构建一个高效的预言机；其次，他们使用这个预言从一组有限的临界值中找到最佳值。我们提出了一种新颖的方法，可以避免决策版本的弯路。这给出了多面体距离函数（例如，和）下多边形曲线之间的 Fréchet 距离的第一个二次时间算法。我们还得到了欧几里德度量下的 Fréchet 距离的近似值，对于任何固定的二次时间。对于精确的欧几里德情况，我们的框架目前生成一个具有运行时间的算法。然而，我们推测它最终可能会带来更快的精确算法。
All known algorithms for the Fréchet distance between curves proceed in two steps: first, they construct an efficient oracle for the decision version; second, they use this oracle to find the optimum from a finite set of critical values. We present a novel approach that avoids the detour through the decision version. This gives the first quadratic time algorithm for the Fréchet distance between polygonal curves inunder polyhedral distance functions (e.g.,and). We also get a-approximation of the Fréchet distance under the Euclidean metric, in quadratic time for any fixed. For the exact Euclidean case, our framework currently yields an algorithm with running time. However, we conjecture that it may eventually lead to a faster exact algorithm.
登录
查看更多内容
Frechet距离的重新审视和扩展
DOI：
--
发表时间：
2012
期刊：
影响因子：
--
作者：
Sariel Har;Benjamin Raichel
通讯作者：
Benjamin Raichel
更快的动态堆及其在广播调度中的应用
DOI：
--
发表时间：
2001
期刊：
ACM-SIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
Haim Kaplan;R. Tarjan;Kostas Tsioutsiouliklis
通讯作者：
Kostas Tsioutsiouliklis
具有最佳查询时间的动态平面凸包
DOI：
--
发表时间：
2000
期刊：
Scandinavian Workshop on Algorithm Theory
影响因子：
--
作者：
G. Brodal;R. Jacob
通讯作者：
R. Jacob
近似线性时间内真实曲线的 Fréchet 距离
影响因子：
0.8
作者：
Anne Driemel;Sariel Har;C. Wenk
通讯作者：
C. Wenk
四名苏联人遛狗——阿尔特猜想的应用
DOI：
10.1137/1.9781611973402.103
发表时间：
2012
期刊：
ArXiv
影响因子：
--
作者：
K. Buchin;M. Buchin;Wouter Meulemans;Wolfgang Mulzer
通讯作者：
Wolfgang Mulzer