The continuous Frechet distance between two polygonal curves is classically computed by exploring their free space diagram. Recently, Har-Peled, Raichel, and Robson [SoCG'25] proposed a radically different approach: instead of directly traversing the continuous free space, they approximate the distance by computing paths in a discrete graph derived from the discrete free space, recursively bisecting edges until the discrete distance converges to the continuous Frechet distance. They implement this so-called frog-based technique and report substantial practical speedups over the state of the art. We revisit the frog-based approach and address three of its limitations. First, the method does not compute the Frechet distance exactly. Second, the recursive bisection procedure only introduces the monotonicity events required to realise the Frechet distance asymptotically, that is, only in the limit. Third, the applied simplification technique is heuristic. Motivated by theoretical considerations, we develop new techniques that guarantee exactness, polynomial-time convergence, and near-optimal lossless simplifications. We provide an open-source C++ implementation of our variant. Our primary contribution is an extensive empirical evaluation. As expected, exact computation introduces overhead and increases the median running time. Yet, our method is often faster in the worst case, the slowest ten percent of instances, or even on average due to its convergence guarantees. More surprisingly, in our experiments, the implementation of Bringmann, Kuennemann, and Nusser [SoCG'19] consistently outperforms all frog-based approaches in practice. This appears to contrast published claims of the efficiency of the frog-based techniques. These results thereby provide nuanced perspective on frogs: highlighting both the theoretical appeal, but also the practical limitations.

翻译：两条多边形曲线间的连续弗雷歇距离传统上通过探索其自由空间图进行计算。最近，Har-Peled、Raichel和Robson [SoCG'25] 提出了一种根本不同的方法：不直接遍历连续自由空间，而是通过计算从离散自由空间导出的离散图中的路径来逼近距离，递归地对边进行二分直到离散距离收敛于连续弗雷歇距离。他们实现了这种所谓的蛙跳技术，并报告了相对于现有技术显著的实践加速。我们重新审视了蛙跳方法，并解决了其三个局限性。首先，该方法无法精确计算弗雷歇距离。其次，递归二分过程仅渐近地（即在极限情况下）引入实现弗雷歇距离所需的单调性事件。第三，所应用的简化技术是启发式的。基于理论考量，我们开发了保证精确性、多项式时间收敛性和接近最优无损简化的新技术。我们提供了我们变体的开源C++实现。我们的主要贡献是广泛的实证评估。正如预期，精确计算引入了开销并增加了中位数运行时间。然而，由于我们的方法具有收敛保证，在最坏情况、最慢的10%实例甚至平均情况下，它通常更快。更令人惊讶的是，在我们的实验中，Bringmann、Kuennemann和Nusser [SoCG'19] 的实现始终在实践中优于所有蛙跳方法。这似乎与已发表的关于蛙跳技术效率的声明形成对比。因此，这些结果为蛙跳算法提供了细致的视角：既突出了其理论吸引力，也揭示了其实际局限性。