Four Soviets Walk the Dog - with an Application to Alt's Conjecture
Four Soviets Walk the Dog - with an Application to Alt's Conjecture
复制标题
四名苏联人遛狗——阿尔特猜想的应用
DOI：
10.1137/1.9781611973402.103
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Wolfgang Mulzer
中科院分区：
文献类型：
--
作者：
K. Buchin;M. Buchin;Wouter Meulemans;Wolfgang Mulzer
给定平面上的两条多边形曲线，有许多方法可以定义它们之间的相似性。一个非常流行的测量方法是弗雷歇距离。自从Alt和Godau于1992年提出以来，已经研究了许多变体和扩展。尽管如此，即使在20多年后，Alt和Godau用于计算Frechet距离的原始O（n2 log n）算法仍然是最先进的（这里n表示每条曲线上的顶点数）。这导致Helmut Alt猜想相关的决策问题是3SUM-困难的。
在最近的工作中，Agarwal等人展示了如何打破离散版本的弗雷歇距离的二次障碍，其中考虑点序列而不是多边形曲线。建立在他们的工作，我们给出了一个随机算法来计算两个多边形曲线之间的Frechet距离在时间[方程]上的指针机器和时间O（n2（log log n）2）字RAM。此外，我们证明了存在一个代数决策树的决策问题的深度为O（n2-e），对于某些e > 0。这提供了决策问题可能不是3SUM困难的证据，并揭示了这个研究充分的问题的一个有趣的新方面。
Given two polygonal curves in the plane, there are many ways to define a notion of similarity between them. One measure that is extremely popular is the Frechet distance. Since it has been proposed by Alt and Godau in 1992, many variants and extensions have been studied. Nonetheless, even more than 20 years later, the original O(n2 log n) algorithm by Alt and Godau for computing the Frechet distance remains the state of the art (here n denotes the number of vertices on each curve). This has led Helmut Alt to conjecture that the associated decision problem is 3SUM-hard.
In recent work, Agarwal et al. show how to break the quadratic barrier for the discrete version of the Frechet distance, where one considers sequences of points instead of polygonal curves. Building on their work, we give a randomized algorithm to compute the Frechet distance between two polygonal curves in time [EQUATION] on a pointer machine and in time O(n2(log log n)2) on a word RAM. Furthermore, we show that there exists an algebraic decision tree for the decision problem of depth O(n2-e), for some e > 0. This provides evidence that the decision problem may not be 3SUM-hard after all and reveals an intriguing new aspect of this well-studied problem.
使用可伸缩皮带计算 Fréchet 距离
影响因子：
0.8
作者：
Kevin Buchin;Maike Buchin;Rolf van Leusden;Wouter Meulemans;Wolfgang Mulzer
通讯作者：
Wolfgang Mulzer