Approximating the geometric edit distance

DOI10.1007/s00453-022-00966-4OpenAlexW2991611170MaRDI QIDQ2165024

Xinyi Li, Kyle Fox

Publication date: 18 August 2022

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1910.00773

zbMATH Keywords

computational geometryapproximation algorithmsgeometric edit eistanceordered sequences measurements

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Cites Work

• A faster algorithm computing string edit distances
• An improved approximation algorithm for the discrete Fréchet distance
• Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)
• Approximability of the discrete Fréchet distance
• Approximating Dynamic Time Warping and Edit Distance for a Pair of Point Sequences
• Algorithms for approximate string matching
• Incremental String Comparison
• The String-to-String Correction Problem
• Dynamic Time Warping and Geometric Edit Distance
• Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity
• Dynamic Time Warping in Strongly Subquadratic Time: Algorithms for the Low-Distance Regime and Approximate Evaluation
• On the complexity of \(k\)-SAT
• Unnamed Item

This page was built for publication: Approximating the geometric edit distance