论文标题
翻转弗里切特的距离
On Flipping the Fréchet distance
论文作者
论文摘要
两条曲线之间的经典和广泛研究的Fréchet距离被定义为INF最大值，其中量最大在曲线的所有遍历上，并且最大值在两个代理的所有并发位置上。在本文中，我们调查了由SUP MIN定义的“翻转”Fréchet度量 - 上限是曲线的所有遍历，而最小值是两个代理的所有并发位置。这项措施在两个曲线（或一般域）之间产生了“社会距离”的概念，在这些曲线（或一般域）中，试图保持尽可能远的同时穿越曲线。 我们首先研究了一个和二维的两个多边形曲线之间的翻转Fréchet度量，提供了条件下限和匹配算法。然后，我们在多边形上考虑这种度量，其中它表示两个代理可以在限制在同一多边形边界或在同一多边形边界上的最小距离。我们在这种情况下研究了问题的几种变体，其中一些我们提供了线性时间算法。最后，我们将此度量考虑在图表上。 我们在计算几何形状中提出的翻转Fréchet测度与现有相关工作之间建立了联系，希望我们的新措施可以产生类似于Fréchet距离的调查，并培养出出现的进一步有趣的问题。
The classical and extensively-studied Fréchet distance between two curves is defined as an inf max, where the infimum is over all traversals of the curves, and the maximum is over all concurrent positions of the two agents. In this article we investigate a "flipped" Fréchet measure defined by a sup min -- the supremum is over all traversals of the curves, and the minimum is over all concurrent positions of the two agents. This measure produces a notion of "social distance" between two curves (or general domains), where agents traverse curves while trying to stay as far apart as possible. We first study the flipped Fréchet measure between two polygonal curves in one and two dimensions, providing conditional lower bounds and matching algorithms. We then consider this measure on polygons, where it denotes the minimum distance that two agents can maintain while restricted to travel in or on the boundary of the same polygon. We investigate several variants of the problem in this setting, for some of which we provide linear time algorithms. Finally, we consider this measure on graphs. We draw connections between our proposed flipped Fréchet measure and existing related work in computational geometry, hoping that our new measure may spawn investigations akin to those performed for the Fréchet distance, and into further interesting problems that arise.
