3 papers
cs.CG2026
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…
cs.CG2026
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…
cs.CG2025
Algorithms and Lower Bounds for the Maximum Overlap of Two Polygons Under Translation
Mikkel Abrahamsen, Sujoy Bhore, Maike Buchin +4
A fundamental problem in shape matching and geometric similarity is computing the maximum area overlap between two polygons under translation. For general simple polygons, the best…