6 papers
A Constant-Factor Approximation for Continuous Dynamic Time Warping in 2D
Kevin Buchin, Maike Buchin, Jan Erik Swiadek +1
Continuous Dynamic Time Warping (CDTW) is a robust similarity measure for polygonal curves that has recently found a variety of applications. Despite its practical use, not much is…
Fundamentals of Computing Continuous Dynamic Time Warping in 2D under Different Norms
Kevin Buchin, Maike Buchin, Jan Erik Swiadek +1
Continuous Dynamic Time Warping (CDTW) measures the similarity of polygonal curves robustly to outliers and to sampling rates, but the design and analysis of CDTW algorithms face m…
Euclidean Noncrossing Steiner Spanners of Nearly Optimal Sparsity
Sujoy Bhore, Sándor Kisfaludi-Bak, Lazar MilenkoviÄ +3
A Euclidean noncrossing Steiner -spanner for a point set is a planar straight-line graph that, for any two points , contains a path whose…
Property Testing of Curve Similarity
Peyman Afshani, Maike Buchin, Anne Driemel +2
We propose sublinear algorithms for probabilistic testing of the discrete and continuous Fréchet distance - a standard similarity measure for curves. We assume the algorithm is gi…
Faster Fréchet Distance under Transformations
Kevin Buchin, Maike Buchin, Zijin Huang +2
We study the problem of computing the Fréchet distance between two polygonal curves under transformations. First, we consider translations in the Euclidean plane. Given two curves…
Computing Oriented Spanners and their Dilation
Kevin Buchin, Antonia Kalb, Anil Maheshwari +4
Given a point set in a metric space and a real number , an \emph{oriented -spanner} is an oriented graph , where for eve…