2026/07/24 by Anders Aamand, Mikkel Abrahamsen, Simon Bartlmae +3
#cs.CG #cs.DS
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 for decades [Baker and Schwarz, SICOMP 1983], the current best algorithm for convex polygons has competitive ratio O(nlog2 3-1log n) = O(n0.59), where n is the number of polygons. This algorithm was described by Aamand, Abrahamsen, Beretta, and Kleist [SODA 2023], who also proved a lower bound of Ω(√(log n/loglog n)) on the competitive ratio of any algorithm. Their lower bound is obtained via a reduction from online sorting, a problem introduced in the same paper, for which they established a lower bound on the competitive ratio. We introduce a new, natural online problem that we call online TSP scheduling. Here, points x1,…,xn arrive online from a metric space (M,d), and upon arrival each xi must be assigned a visit time pi∈[0,∞) satisfying |pi-pj|≥ d(xi,xj) for all j<i. The cost of the schedule is maxi pi. We present an O(log2 n)-competitive algorithm for online TSP scheduling, and show how this implies an O(log2 n)-competitive algorithm for online translational strip packing of convex polygons. We also prove that the same competitive ratio is achievable for other translational packing problems, including online packing of d-dimensional unit hyperdisks in \mathbb Rd+1, whose offline version was studied by Alt, Cabello, Cheong, Park, and Seiferth [Comp. Geom. 2026]. Our algorithm for online TSP scheduling builds on a recent breakthrough for online sorting by Azar, Panigrahi, and Vardi [SODA 2026]. We thus show that the connection between packing and online sorting can be used not only for lower bounds, but also for algorithms.