2026-07-23T13:08:55Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:21099 2024-09-23T09:13:16Z ddc:004 open_access

A Faster Algorithm for the Fréchet Distance in 1D for the Imbalanced Case Blank, Lotte Driemel, Anne {Fréchet distance} distance oracle data structures time series The fine-grained complexity of computing the {Fréchet distance } has been a topic of much recent work, starting with the quadratic SETH-based conditional lower bound by Bringmann from 2014. Subsequent work established largely the same complexity lower bounds for the {Fréchet distance } in 1D. However, the imbalanced case, which was shown by Bringmann to be tight in dimensions d ≥ 2, was still left open. Filling in this gap, we show that a faster algorithm for the {Fréchet distance } in the imbalanced case is possible: Given two 1-dimensional curves of complexity n and n^{α} for some α ∈ (0,1), we can compute their {Fréchet distance } in O(n^{2α} log² n + n log n) time. This rules out a conditional lower bound of the form O((nm)^{1-ε}) that Bringmann showed for d ≥ 2 and any ε > 0 in turn showing a strict separation with the setting d = 1. At the heart of our approach lies a data structure that stores a 1-dimensional curve P of complexity n, and supports queries with a curve Q of complexity m for the continuous {Fréchet distance } between P and Q. The data structure has size in 𝒪(nlog n) and uses query time in 𝒪(m² log² n). Our proof uses a key lemma that is based on the concept of visiting orders and may be of independent interest. We demonstrate this by substantially simplifying the correctness proof of a clustering algorithm by Driemel, Krivošija and Sohler from 2015. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Lotte Blank and Anne Driemel 2024 Is Part Of LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2024.28 urn:nbn:de:0030-drops-210999 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.28 eng https://creativecommons.org/licenses/by/4.0/legalcode