6 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…
Touring a Sequence of Orthogonal Polygons
Katrin Casel, Sándor Kisfaludi-Bak, Linda Kleist +3
We study the problem of computing a shortest tour that visits a sequence of polygons with a total number of vertices. A tour is an oriented curve such that…
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…
Flip Distance of Non-Crossing Spanning Trees: NP-Hardness and Improved Bounds
HÃ¥vard Bakke Bjerkevik, Joseph Dorfer, Linda Kleist +2
We consider the problem of reconfiguring non-crossing spanning trees on point sets. For a set of points in general position in the plane, the flip graph has a vertex…
Online Packing of Orthogonal Polygons
Tim Gerlach, Benjamin Hennies, Linda Kleist
While rectangular and box-shaped objects dominate the classic discourse of theoretic investigations, a fascinating frontier lies in packing more complex shapes. Given recent insigh…
Reconfiguration of unit squares and disks: PSPACE-hardness in simple settings
Mikkel Abrahamsen, Kevin Buchin, Maike Buchin +5
We study two well-known reconfiguration problems. Given a start and a target configuration of geometric objects in a polygon, we wonder whether we can move the objects from the sta…