4 papers · 2 filters
On (Directed) Width-Parameters of Geometric Spanners
Kevin Buchin, Carolin Rehs, Torben Scheele
To speed up algorithms on geometric graphs, it is common to approximate the complete Euclidean graph while maintaining certain geometric properties. A (directed) -spanner fo…
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…