SETH Says: Weak Fréchet Distance is Faster, but only if it is Continuous and in One Dimension

Kevin Buchin, Tim Ophelders, Bettina Speckmann

Type: Preprint

Publication Date: 2018-01-01

Citations: 0

DOI: https://doi.org/10.48550/arxiv.1807.08699

View Publication

Locations

arXiv (Cornell University) - View - PDF
DataCite API - View

Similar Works

Action	Title	Year	Authors
+ PDF Chat	SETH Says: Weak Fréchet Distance is Faster, but only if it is Continuous and in One Dimension	2019	Kevin Buchin Tim Ophelders Bettina Speckmann
+	Approximability of the discrete Fréchet distance	2016	Karl Bringmann Wolfgang Mulzer
+	Approximability of the Discrete Fréchet Distance	2015	Karl Bringmann Wolfgang Mulzer
+	A Subquadratic $n^ε$-approximation for the Continuous Fréchet Distance	2022	Thijs van der Horst Marc van Kreveld Tim Ophelders Bettina Speckmann
+	Data Structures for Approximate Discrete Fréchet Distance	2022	Ivor van der Hoog Eva Rotenberg Sampson Wong
+ PDF Chat	Four Soviets Walk the Dog: Improved Bounds for Computing the Fréchet Distance	2017	Kevin Buchin Maike Buchin Wouter Meulemans Wolfgang Mulzer
+ PDF Chat	Why Walking the Dog Takes Time: Frechet Distance Has No Strongly Subquadratic Algorithms Unless SETH Fails	2014	Karl Bringmann
+	Why walking the dog takes time: Frechet distance has no strongly subquadratic algorithms unless SETH fails	2014	Karl Bringmann
+	Why walking the dog takes time: Frechet distance has no strongly subquadratic algorithms unless SETH fails	2014	Karl Bringmann
+ PDF Chat	A faster algorithm for the Fr\'echet distance in 1D for the imbalanced case	2024	Lotte Blank Anne Driemel
+	Improved approximation for Fréchet distance on c-packed curves matching conditional lower bounds	2014	Karl Bringmann Marvin Künnemann
+ PDF Chat	On optimal approximability results for computing the strong metric dimension	2017	Bhaskar DasGupta Nasim Mobasheri
+	Improved approximation for Fr\'echet distance on c-packed curves matching conditional lower bounds	2014	Karl Bringmann Marvin Künnemann
+	The exact bound for the reverse isodiametric problem in 3-space	2024	Arkadiy Aliev
+	On the Discrete Fréchet Distance in a Graph	2022	Anne Driemel Ivor van der Hoog Eva Rotenberg
+	A Subquadratic <i>n</i><sup>ε</sup>-approximation for the Continuous Fréchet Distance	2023	Thijs van der Horst Marc van Kreveld Tim Ophelders Bettina Speckmann
+	Tight Bounds for Approximate Near Neighbor Searching for Time Series under the Fréchet Distance	2021	Karl Bringmann Anne Driemel André Nusser Ioannis Psarros
+ PDF Chat	Distance sets, orthogonal projections and passing to weak tangents	2018	Jonathan M. Fraser
+	Approximating the (continuous) Fr\'echet distance	2020	Connor Colombe Kyle Fox
+	Approximating the (Continuous) Fréchet Distance	2020	Connor Colombe Kyle Fox

Works That Cite This (0)

Action	Title	Year	Authors

Works Cited by This (0)

Action	Title	Year	Authors