Faster Fréchet Distance Approximation Through Truncated Smoothing

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Abstract

The Fréchet distance is a popular distance measure for curves. Computing the Fréchet distance between two polygonal curves of n vertices takes roughly quadratic time, and conditional lower bounds suggest that even approximating to within a factor 3 cannot be done in strongly-subquadratic time, even in one dimension. The current best approximation algorithms present trade-offs between approximation quality and running time. Recently, van der Horst et al. (SODA, 2023) presented an O((n2/α) log3 n) time α-approximate algorithm for curves in arbitrary dimensions, for any α ∈ [1, n]. Our main contribution is an approximation algorithm for curves in one dimension, with a significantly faster running time of O(n log3 n + (n23) log2 n log log n). Additionally, we give an algorithm for curves in arbitrary dimensions that improves upon the state-of-the-art running time by a logarithmic factor, to O((n2/α) log2 n). Both of our algorithms rely on a linear-time simplification procedure that in one dimension reduces the complexity of the reachable free space to O(n2/α) without making sacrifices in the asymptotic approximation factor.

Original languageEnglish
Title of host publication40th International Symposium on Computational Geometry (SoCG 2024)
EditorsWolfgang Mulzer, Jeff M. Phillips
PublisherSchloss Dagstuhl -- Leibniz-Zentrum für Informatik
Pages63:1-63:15
Number of pages15
ISBN (Electronic)978-3-95977-316-4
ISBN (Print)978-3-95977-316-4
DOIs
Publication statusPublished - 6 Jun 2024

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume293
ISSN (Print)1868-8969

Keywords

  • Frécht distance
  • approximation algorithms
  • simplification

Fingerprint

Dive into the research topics of 'Faster Fréchet Distance Approximation Through Truncated Smoothing'. Together they form a unique fingerprint.

Cite this