Computing Fr\'echet distance between two\Frd curves takes roughly quadratic time. In this paper, we show that for curves with long edges the Fr\'echet distance computations become easier. Let P and Q be two polygonal curves in \mathbb{R \Reals ^d with n and m vertices, respectively. We prove four main results for the case when all edges of both curves are long compared to the Fr\'echet distance between them: (1) a linear-time algorithm for deciding the Fr\'echet distance between two curves, (2) an algorithm that computes the Fr\'echet distance \Frd in O((n+m)\log (n+m)) time, (3) a linear-time d -approximation algorithm, and (4) a data structure that supports O(m\log^2 n)-time decision queries, where m is the number of vertices of the query curve and n the number of vertices of the preprocessed curve.
Computing the~\Frd\ between two polygonal curves takes roughly quadratic time. In this paper, we show that for a special class of curves the Fr\'echet distance computations become easier. Let P and Q be two polygonal curves in \Reals ^d with n and m vertices, respectively. We prove four results for the case when all edges of both curves are long compared to the Fr\'echet distance between them: (1) a linear-time algorithm for deciding the Fr\'echet distance between two curves, (2) an algorithm that computes the \Frd\ in O((n+m)\log (n+m)) time, (3) a linear-time d -approximation algorithm, and (4) a data structure that supports O(m\log^2 n)-time decision queries, where m is the number of vertices of the query curve and n the number of vertices of the preprocessed curve.
R
Fr\'echet distance between two
the~
A
\ between two polygonal
R
curves with long edges
a special class of curves
D
\mathbb{R
D
main
D
Fr\'echet distance
A
\