7 papers
Online Geometric Packing through Online TSP Scheduling
Anders Aamand, Mikkel Abrahamsen, Simon Bartlmae +3
We consider the problem of online packing of convex polygons into a strip by translations. While online algorithms with a constant competitive ratio have been known for rectangles…
Covering and Partitioning Complex Objects with Small Pieces
Anders Aamand, Mikkel Abrahamsen, Reilly Browne +6
We study the problems of covering or partitioning a polygon (possibly with holes) using a minimum number of small pieces, where a small piece is a connected sub-polygon contain…
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…
Bounding a Polygon by a Minimum Number of Vertices
Mikkel Abrahamsen, Jack Stade, Shuyi Yan +1
Suppose that a polygon is given as an array containing the vertices in counterclockwise order. We analyze how many vertices (including the index of each of these vertices) we n…
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…