Solving Fréchet Distance Problems by Algebraic Geometric Methods

2023/08/28 by Cheng, Siu-Wing, Huang, Haoqiang · 1 citation
#Computational Geometry (cs.CG) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2308.14569

Abstract

We study several polygonal curve problems under the Fréchet distance via algebraic geometric methods. Let \mathbbX_m^d and \mathbbX_k^d be the spaces of all polygonal curves of m and k vertices in ℝ^d, respectively. We assume that k ≤ m. Let R^d_k,m be the set of ranges in \mathbbX_m^d for all possible metric balls of polygonal curves in \mathbbX_k^d under the Fréchet distance. We prove a nearly optimal bound of O(dklog (km)) on the VC dimension of the range space (\mathbbX_m^d,R_k,m^d), improving on the previous O(d²k²log(dkm)) upper bound and approaching the current Ω(dklog k) lower bound. Our upper bound also holds for the weak Fréchet distance. We also obtain exact solutions that are hitherto unknown for curve simplification, range searching, nearest neighbor search, and distance oracle.

Cited by

• Improved Learning via k-DTW: A Novel Dissimilarity Measure for Curves

Related

• Hardness Results on Curve/Point Set Matching with Fréchet Distance
• The k-Fréchet distance
• Frechet similarity of closed polygonal curves
• Similarity of closed polygonal curves in Frechet metric
• Fast Frechet Distance Between Curves With Long Edges