Fr\'echet Distance in Subquadratic Time
<|reference_start|>Fr\'echet Distance in Subquadratic Time: Let $m$ and $n$ be the numbers of vertices of two polygonal curves in $\mathbb{R}^d$ for any fixed $d$ such that $m \leq n$. Since it was known in 1995 how to compute the Fr\'{e}chet distance of these two curves in $O(mn\log (mn))$ time, it has been an open problem whether the running time can be reduced to $o(n^2)$ when $m = \Omega(n)$. In the mean time, several well-known quadratic time barriers in computational geometry have been overcome: 3SUM, some 3SUM-hard problems, and the computation of some distances between two polygonal curves, including the discrete Fr\'{e}chet distance, the dynamic time warping distance, and the geometric edit distance. It is curious that the quadratic time barrier for Fr\'{e}chet distance still stands. We present an algorithm to compute the Fr\'echet distance in $O(mn(\log\log n)^{2+\mu}\log n/\log^{1+\mu} m)$ expected time for some constant $\mu \in (0,1)$. It is the first algorithm that returns the Fr\'{e}chet distance in $o(mn)$ time when $m = \Omega(n^{\varepsilon})$ for any fixed $\varepsilon \in (0,1]$.<|reference_end|>
@article{cheng2024fr\'echet,
    title={Fr\'echet Distance in Subquadratic Time},
    author={Siu-Wing Cheng, Haoqiang Huang},
    journal={arXiv preprint arXiv:2407.05231},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.05231},
    primaryClass={cs.CG cs.DS}
}