论文标题
在离散的fréchet距离上
On the Discrete Fréchet Distance in a Graph
论文作者
论文摘要
Fréchet距离是曲线之间广泛研究的相似性度量，在整个计算机科学中广泛使用。由应用曲线源于基础图（例如道路网络）的路径和行走的应用，我们定义并研究了弗雷奇特距离的距离，以在图形上进行路径和行走。当提供带有$ o（1）$查询时间的$ g $的距离甲骨文时，经典的二次时间动态程序可以计算$ o（| p | \ cdot | q |）$ in Graph $ g $中的两个步行$ p $和$ q $之间的fréchet距离。我们表明，在某些情况下，图形结构有助于计算fréchet距离：当图$ g $是平面时，我们应用现有的（近似）距离甲骨文来计算$（1+ \ varepsilon）$ - fréchet距离的近似值 - 最短路径$ p $和任何步行$ q $ in $ o（ | P |。我们将此结果推广到最短的路径，即$κ$ -straight路径，因为我们展示了如何计算$κ$ -straight Path $ p $与任何步行$ q $ in $ o（| g | g | g | g | / \ sqrt { \ frac {κ| q |} {\ varepsilon}）$时间。我们在$ g $中最短的路径度量标准的强度和弱离散距离的算法结果都可以。最后，我们表明输入上的其他假设，例如我们对路径直度的假设，确实需要获得真正的亚二次运行时间。我们提供了有条件的下限，表明Fréchet的距离，甚至是其1.01美元的AppRximation，在加权平面图中任意\ Emph {paths}之间的距离无法在$ o中计算，除非任何$δ> 0 $δ> 0 $δ> 0 $δ> 0 $δ> 0 $ upothesiss ofthogosonal vector bythesiss $ o（（| p | \ cdot | q | q | q |）^{1-δ}）$。对于散步，即使$ g $是平面，单位重量，并且具有$ o（1）$ dertices，则该下限也可以。
The Fréchet distance is a well-studied similarity measure between curves that is widely used throughout computer science. Motivated by applications where curves stem from paths and walks on an underlying graph (such as a road network), we define and study the Fréchet distance for paths and walks on graphs. When provided with a distance oracle of $G$ with $O(1)$ query time, the classical quadratic-time dynamic program can compute the Fréchet distance between two walks $P$ and $Q$ in a graph $G$ in $O(|P| \cdot |Q|)$ time. We show that there are situations where the graph structure helps with computing Fréchet distance: when the graph $G$ is planar, we apply existing (approximate) distance oracles to compute a $(1+\varepsilon)$-approximation of the Fréchet distance between any shortest path $P$ and any walk $Q$ in $O(|G| \log |G| / \sqrt{\varepsilon} + |P| + \frac{|Q|}{\varepsilon } )$ time. We generalise this result to near-shortest paths, i.e. $κ$-straight paths, as we show how to compute a $(1+\varepsilon)$-approximation between a $κ$-straight path $P$ and any walk $Q$ in $O(|G| \log |G| / \sqrt{\varepsilon} + |P| + \frac{κ|Q|}{\varepsilon } )$ time. Our algorithmic results hold for both the strong and the weak discrete Fréchet distance over the shortest path metric in $G$. Finally, we show that additional assumptions on the input, such as our assumption on path straightness, are indeed necessary to obtain truly subquadratic running time. We provide a conditional lower bound showing that the Fréchet distance, or even its $1.01$-approximation, between arbitrary \emph{paths} in a weighted planar graph cannot be computed in $O((|P|\cdot|Q|)^{1-δ})$ time for any $δ> 0$ unless the Orthogonal Vector Hypothesis fails. For walks, this lower bound holds even when $G$ is planar, unit-weight and has $O(1)$ vertices.
