Solving Fréchet Distance Problems by Algebraic Geometric Methods
Siu-Wing Cheng, Haoqiang Huang · Society for Industrial and Applied Mathematics eBooks · 2024
We study several polygonal curve problems under the Fréchet distance via algebraic geometric methods. Let 𝕏dm and 𝕏dk be the spaces of all polygonal curves of m and k vertices in ℝd, respectively. We assume that k ≤ m. Let be the set of ranges in 𝕏dm for all possible metric balls of polygonal curves in 𝕏dk under the Fréchet distance. We prove a nearly optimal bound of O(dk log(km)) on the VC dimension of the range space (𝕏dm, ), improving on the previous O(d2k2 log(dkm)) upper bound and approaching the current Ω(dk log k) lower bound. Our upper bound also holds for the weak Fréchet distance. We also obtain exact solutions that are hitherto unknown for the curve simplification, range searching, nearest neighbor search, and distance oracle problems.