4 papers
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…
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…