Solving Fréchet Distance Problems by Algebraic Geometric Methods

We study several polygonal curve problems under the Fréchet distance via algebraic geometric methods. Let X d m and X d k be the spaces of all polygonal curves of m and k vertices in R d , respectively. We assume that k ≤ m. Let R d k,m be the set of ranges in X d m for all possible metric balls of polygonal curves in X d k under the Fréchet distance. We prove a nearly optimal bound of O(dk log(km)) on the VC dimension of the range space (X d m , R d k,m ), improving on the previous O(d 2 k 2 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.