A Strongly-Subquadratic (3 + ε)-Approximation for the Fréchet Distance for Paths in Metric Spaces

Jul 16, 2026

Upload by Riley

Fréchet distance provides an ordered, metric-based measure of similarity between two paths and is widely studied, yet exact computation for polylines is near-quadratic in the vertex counts. Under SETH, it cannot be approximated within factor 3 in strongly-subquadratic time. The work presents a deterministic approach that computes a (3+ε)-approximation in strongly-subquadratic time, closely matching the SETH-implied conditional lower bound. It also derives a 3-approximation for one-dimensional polylines in R that exactly matches the conditional bound, using a general strongly-subquadratic decision procedure based on free-space properties.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages18

Reading Time45 min

Abstract

Introduction

Background and Related Work

Problem Setting and Prior Bounds

Summary of Results

arXiv :2607 .08893v 1 [ cs .CG] 9 Jul 2026 A Strongly-Subquadratic (3 + ε)-Approximation for the Fréchet Distance for Paths in Metric Spaces Thijs van der Horst \# Department of Information and Computing Sciences, Utrecht University, the Netherlands Department of Mathematics and Computer Science, TU Eindhoven, the Netherlands Tim Ophelders \# Department of Mathematics and Computer Science, TU Eindhoven, the Netherlands ~~ Abstract ~~ The Fréchet distance is a well-studied distance measure for paths in a metric space. It is mostly studied for paths in d-dimensional Euclidean space. Here, computing the Fréchet distance between two polylines takes time roughly quadratic in the number of vertices. Assuming the strong exponential time hypothesis (SETH), it cannot be approximated to within a factor less than 3 in stronglysubquadratic time. Recently, it was shown that for any ε > 0, there exists a randomized algorithm that can compute a (7 + ε)-approximation in strongly-subquadratic expected time [Cheng, Huang, and Zhang; STOC’25] . For polylines with n and m vertices in a Euclidean space of constant dimension, where n ≥ m, their algorithm takes O (nm0 .99 log(n/ε)) time in expectation. We present a deterministic approximation algorithm that significantly improves upon the approximation factor and running time. Specifically, our algorithm computes a (3 + ε)-approximation in O(nm2/3 log n · log( 1ε log n)) time. Our algorithm nearly matches the conditional lower bound on the approximation factor implied by SETH. For polylines in R, we present a 3-approximation algorithm that runs in O(nm2/3 log5/3 n) time, and exactly matches the conditional lower bound. For our results, we introduce a general strongly-subquadratic time 3-approximate decision algorithm. This algorithm makes no assumptions on the ambient metric space, and relies only on standard assumptions on the so-called free space of the input paths. Under some mild assumptions, our decision algorithm leads to a (3 + ε)-approximation algorithm in general metric spaces. These assumptions hold automatically for polylines in any metric space (Rd , Lp) with p ≥ 1. 2012 ACM Subject Classification Theory of computation → Computational Geometry Keywords and phrases Fréchet distance, path similarity, approximation algorithm Funding Tim Ophelders: partially supported by the Dutch Research Council (NWO) under project no. VI.Vidi.243.236. 2 A Strongly-Subquadratic (3 + ε)-Approximation for the Fréchet Distance 1 Introduction The Fréchet distance is a well-studied distance measure for paths in a metric space, used to determine the similarity of two paths. Measuring similarity is an important task in for example matching time series in data bases [14], protein alignment [13], and trajectory analysis [18] . The Fréchet distance is more discriminative than, e.g. , the Hausdorff distance, as it takes into account the intrinsic ordering of the points on a path. Alt and Godau [1] were the first to study the computability of the Fréchet distance. They showed that one can compute the Fréchet distance between two polylines in Rd , under some Lp norm with p ≥ 1, in O (nm log n) time, where n and m are the number of vertices of the polylines and n ≥ m. Since their result, only marginal improvements have been made [5, 7], shaving off mere polylogarithmic factors. The lack of significant improvements can be explained by the widely-believed strong exponential time hypothesis (SETH) . Bringmann [3] proved that assuming SETH, the Fréchet distance cannot be comp˜uted in strongly-subquadratic time; i.e. , O((nm)1−δ ) time for any δ > 0. Moreover, for n = Θ(m), Buchin, Ophelders, and Speckmann [6] showed that the Fréchet distance cannot be approximated better than within a factor 3 in strongly-subquadratic time, even for d = 1 . The conditional lower bound raises the question of how well the Fréchet distance can be approximated in strongly-subquadratic time. For polylines in (

FAQs

What is the main problem addressed in the document?

Computing or approximating the Fréchet distance between two polylines efficiently, specifically in strongly-subquadratic time.

How does SETH affect what approximation factors are achievable?

Assuming SETH, the document states that approximating the Fréchet distance to within a factor less than 3 in strongly-subquadratic time is not possible.

What approximation guarantees and running times does the proposed deterministic algorithm provide?

It computes a (3+ε)-approximation with running time O(nm2/3 log n · log(1/(ε log n))). For polylines in R, it provides a 3-approximation in O(nm2/3 log5/3 n) time and matches the conditional lower bound.

Jul 16, 2026

Upload by Riley