Solving Fr'echet Distance Problems by Algebraic Geometric Methods

We study several polygonal curve problems under the Fr'echet distance via algebraic geometric methods. Let mathbbXmd and mathbbXkd be the spaces of all polygonal curves of m and k vertices in ℝd, respectively. We assume that k ≤ m. Let Rdk,m be the set of ranges in mathbbXmd for all possible metric balls of polygonal curves in mathbbXkd under the Fr'echet distance. We prove a nearly optimal bound of O(dklog (km)) on the VC dimension of the range space (mathbbXmd,Rk,md), improving on the previous O(d2k2log(dkm)) upper bound and approaching the current Omega(dklog k) lower bound. Our upper bound also holds for the weak Fr'echet distance. We also obtain exact solutions that are hitherto unknown for curve simplification, range searching, nearest neighbor search, and distance oracle.