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

DOI10.1007/978-3-662-48971-0_44zbMath1372.68252arXiv1408.1340OpenAlexW1796724073MaRDI QIDQ3459889

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)

Related Items (16)

The Complexity of Problems in P Given Correlated Instances ⋮ Computing the longest common almost-increasing subsequence ⋮ Longest common subsequence in sublinear space ⋮ A Linear-Time n ^0.4 -Approximation for Longest Common Subsequence ⋮ On the Complexity of String Matching for Graphs ⋮ Unnamed Item ⋮ Fast and Deterministic Constant Factor Approximation Algorithms for LCS Imply New Circuit Lower Bounds ⋮ A Faster Subquadratic Algorithm for the Longest Common Increasing Subsequence Problem ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A fine-grained analogue of schaefer's Theorem in P: dichotomy of ∃k∀-quantified first-order graph properties ⋮ Fine-Grained Complexity Theory (Tutorial) ⋮ The Orthogonal Vectors Conjecture for Branching Programs and Formulas ⋮ Unnamed Item

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