Abstract

The Fréchet distance stands as a widely-adopted distance function for curves and has found extensive application in trajectory data analysis. Nevertheless, the computational complexity and approximability of this metric still remain to be mysterious. A recent breakthrough in the conditional lower bounds prevents approximating the Fréchet distance within a factor of 3 in strongly subquadratic time. However, the current best strongly subquadratic algorithm attains an approximation ratio that is polynomial in the input size. We make significant progress in bridging the gap between the upper and lower bounds. Specifically, given two polygonal curves of n vertices each, we present an algorithm that can approximate the Fréchet distance between them within a factor of 7+eps. Our algorithm runs in O(n^1.99\log(n/eps)) time, with a success probability at least 1-1/n^6. This is the first algorithm to approximate the Fréchet distance within constant factor in strongly subquadratic time.

Time

2025-03-13 14:00 - 15:00

Speaker

黄浩强

Room

Room 308