6 papers
A Sublinear Approximation Algorithm for Minimum Dilation Trees in the Plane
Sarita de Berg, Jacobus Conradi, Peter Kramer +2
The dilation of a geometric graph measures how much longer the path between pairs of points becomes when restricted to graph edges, rather than following the direct path through th…
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…
Improved Learning via k-DTW: A Novel Dissimilarity Measure for Curves
Amer Krivošija, Alexander Munteanu, André Nusser +1
This paper introduces -Dynamic Time Warping (-DTW), a novel dissimilarity measure for polygonal curves. -DTW has stronger metric properties than Dynamic Time Warping (DTW)…
Computing Non-Obtuse Triangulations with Few Steiner Points
Mikkel Abrahamsen, Florestan Brunck, Jacobus Conradi +2
We present the winning implementation of the Seventh Computational Geometry Challenge (CG:SHOP 2025). The task in this challenge was to find non-obtuse triangulations for given pla…
Clustering with Few Disks to Minimize the Sum of Radii
Mikkel Abrahamsen, Sarita de Berg, Lucas Meijer +2
Given a set of points in the Euclidean plane, the -MinSumRadius problem asks to cover this point set using disks with the objective of minimizing the sum of the radii of…
Minimum Star Partitions of Simple Polygons in Polynomial Time
Mikkel Abrahamsen, Joakim Blikstad, André Nusser +1
We devise a polynomial-time algorithm for partitioning a simple polygon into a minimum number of star-shaped polygons. The question of whether such an algorithm exists has been…