2026-07-24T06:08:33Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23174 2025-10-02T12:41:56Z ddc:004 open_access

Transforming Dogs on the Line: On the Fréchet Distance Under Translation or Scaling in 1D Blank, Lotte Conradi, Jacobus Driemel, Anne Kolbe, Benedikt Nusser, André Richter, Marena Fréchet distance under translation Fréchet distance under scaling time series shape matching The Fréchet distance is a computational mainstay for comparing polygonal curves. The Fréchet distance under translation, which is a translation invariant version, considers the similarity of two curves independent of their location in space. It is defined as the minimum Fréchet distance that arises from allowing arbitrary translations of the input curves. This problem and numerous variants of the Fréchet distance under some transformations have been studied, with more work concentrating on the discrete Fréchet distance, leaving a significant gap between the discrete and continuous versions of the Fréchet distance under transformations. Our contribution is twofold: First, we present an algorithm for the Fréchet distance under translation on 1-dimensional curves of complexity n with a running time of 𝒪(n^{8/3} log³ n). To achieve this, we develop a novel framework for the problem for 1-dimensional curves, which also applies to other scenarios and leads to our second contribution. We present an algorithm with the same running time of 𝒪(n^{8/3} log³ n) for the Fréchet distance under scaling for 1-dimensional curves. For both algorithms we match the running times of the discrete case and improve the previously best known bounds of 𝒪̃(n⁴). Our algorithms rely on technical insights but are conceptually simple, essentially reducing the continuous problem to the discrete case across different length scales. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Lotte Blank and Jacobus Conradi and Anne Driemel and Benedikt Kolbe and André Nusser and Marena Richter 2025 Is Part Of LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2025.22 urn:nbn:de:0030-drops-231746 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.22 eng https://creativecommons.org/licenses/by/4.0/legalcode