Constant Approximation of Fréchet Distance in Strongly Subquadratic Time

2025/03/17 by Cheng, Siu-Wing, Huang, Haoqiang, Zhang, Shuo · 1 citation
#Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2503.12746

Abstract

Let τ and σ be two polygonal curves in ℝ^d for any fixed d. Suppose that τ and σ have n and m vertices, respectively, and m≤ n. While conditional lower bounds prevent approximating the Fréchet distance between τ and σ within a factor of 3 in strongly subquadratic time, the current best approximation algorithm attains a ratio of n^c in strongly subquadratic time, for some constant c∈(0,1). We present a randomized algorithm with running time O(nm^0.99log(n/ε)) that approximates the Fréchet distance within a factor of 7+ε, with a success probability at least 1-1/n⁶. We also adapt our techniques to develop a randomized algorithm that approximates the discrete Fréchet distance within a factor of 7+ε in strongly subquadratic time. They are the first algorithms to approximate the Fréchet distance and the discrete Fréchet distance within constant factors in strongly subquadratic time.

Cited by

• Computing the Fréchet Distance When Just One Curve is c-Packed: A Simple Almost-Tight Algorithm

Related

• (5+ε)-Approximation of Fréchet Distance in Strongly Subquadratic Time
• Fréchet Distance in Subquadratic Time
• A Subquadratic n^ε-approximation for the Continuous Fréchet Distance
• Approximating the (Continuous) Fréchet Distance
• Faster Fréchet distance approximation through truncated smoothing