Improved Approximation for Fréchet Distance on c-packed Curves Matching Conditional Lower Bounds

DOI10.1007/978-3-662-48971-0_44MaRDI QIDQ3459889zbMATH OpenOpenAlexFDO

Authors Karl Bringmann, Marvin Künnemann

Publication date 11 January 2016

Published in Algorithms and Computation (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Abstract: The Fr'echet distance is a well-studied and very popular measure of similarity of two curves. The best known algorithms have quadratic time complexity, which has recently been shown to be optimal assuming the Strong Exponential Time Hypothesis (SETH) [Bringmann FOCS'14]. To overcome the worst-case quadratic time barrier, restricted classes of curves have been studied that attempt to capture realistic input curves. The most popular such class are c-packed curves, for which the Fr'echet distance has a $(1+epsilon)$-approximation in time $ildeO(cn/epsilon)$ [Driemel et al. DCG'12]. In dimension $dge5$ this cannot be improved to $O((cn/sqrtepsilon{)}^{1-delta})$ for any $delta>0$ unless SETH fails [Bringmann FOCS'14]. In this paper, exploiting properties that prevent stronger lower bounds, we present an improved algorithm with runtime $ildeO(cn/sqrtepsilon)$. This is optimal in high dimensions apart from lower order factors unless SETH fails. Our main new ingredients are as follows: For filling the classical free-space diagram we project short subcurves onto a line, which yields one-dimensional separated curves with roughly the same pairwise distances between vertices. Then we tackle this special case in near-linear time by carefully extending a greedy algorithm for the Fr'echet distance of one-dimensional separated curves.

Recommendations

• Improved Approximation for Fréchet Distance on c-Packed Curves Matching Conditional Lower Bounds
• Approximating the Fréchet distance for realistic curves in near linear time
• Approximating the Fréchet distance for realistic curves in near linear time
• Fréchet Distance for Curves, Revisited
• An improved approximation algorithm for the discrete Fréchet distance
• Approximability of the discrete Fréchet distance
• Approximability of the discrete Fréchet distance
• Approximating the Hausdorff distance by \(\alpha\)-dense curves
• Discrete Fréchet distance for closed curves
• scientific article; zbMATH DE number 7051233

Cited in

(21)

• Approximating the packedness of polygonal curves
• Computing the longest common almost-increasing subsequence
• Longest common subsequence in sublinear space
• Towards hardness of approximation for polynomial time problems
• The Complexity of Problems in P Given Correlated Instances
• Fast and deterministic constant factor approximation algorithms for LCS imply new circuit lower bounds
• The Orthogonal Vectors Conjecture for Branching Programs and Formulas
• Fine-Grained Complexity Theory (Tutorial)
• Sketching, streaming, and fine-grained complexity of (weighted) LCS
• On the complexity of string matching for graphs
• A fine-grained analogue of schaefer's Theorem in P: dichotomy of ∃k∀-quantified first-order graph properties
• RLE edit distance in near optimal time
• Tight conditional lower bounds for longest common increasing subsequence
• Improved Approximation for Fréchet Distance on c-Packed Curves Matching Conditional Lower Bounds
• Approximating the Fréchet distance for realistic curves in near linear time
• scientific article; zbMATH DE number 7650079 (Why is no real title available?)
• A Faster Subquadratic Algorithm for the Longest Common Increasing Subsequence Problem
• A Linear-Time n ^0.4 -Approximation for Longest Common Subsequence
• On the Complexity of String Matching for Graphs
• The NFA acceptance hypothesis: non-combinatorial and dynamic lower bounds
• Co-lexicographically ordering automata and regular languages. I

This page was built for publication: Improved Approximation for Fréchet Distance on c-packed Curves Matching Conditional Lower Bounds

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3459889)