7 papers
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…
Computing Hausdorff Distances Under Translations: The Interplay of Dimensionality, Symmetry and Discreteness
Sebastian Angrick, Kevin Buchin, Geri Gokaj +1
To measure the shape similarity of point sets, various notions of the Hausdorff distance under translation are widely studied. In this context, for an -point set and -poi…
Compatible Triangulations of Simple Polygons
Peyman Afshani, Boris Aronov, Kevin Buchin +5
Let and be simple polygons with vertices each. We wish to compute triangulations of and that are combinatorially equivalent, if they exist. We consider two vers…
On Small Pair Decompositions for Point Sets
Kevin Buchin, Jacobus Conradi, Sariel Har-Peled +5
$\newcommand{\Re}{\mathbb{R}}$We study the minWSPD problem of computing the minimum-size well-separated pairs decomposition of a set of points, and show constant approximation algo…
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…