4 papers
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…
Geometric spanners of bounded tree-width
Kevin Buchin, Carolin Rehs, Torben Scheele
Given a point set in the Euclidean space, a geometric -spanner is a graph on such that for every pair of points, the shortest path in between those points is at…