Personal tools
You are here: Home CG seminar 2022 Online Sorting and Translational Packing of Convex Polygons
« August 2022 »
Log in

Forgot your password?

Online Sorting and Translational Packing of Convex Polygons

Wednesday, December 1st, 4:10pm Tel Aviv time (3:10pm CET, 9:10am NY time)


Mikkel Abrahamsen, University of Copenhagen


Packing problems regularly appear in everyday life and also in industrial
settings such as shipping, production of clothing, sheet metal cutting, etc. In
this talk, we investigate various online packing problems in which convex
polygons arrive one by one and have to be placed irrevocably into a container
before the next piece is revealed; the pieces must not be rotated, but only
translated. The aim is to minimize the used space depending on the specific
problem at hand, e.g., the strip length in strip packing, the number of bins in
bin packing, etc.
We draw interesting connections to the following online sorting problem: We
receive a stream of real numbers $s_1, \ldots, s_n$, $s_i \in [0,1]$, one by one.
Each real must be placed in an array $A$ with $Cn$ initially empty cells
without knowing the subsequent reals, for a constant $C\geq 1$. The goal is to
minimize the sum of differences of consecutive reals in $A$. It follows that
the offline optimum is to place the reals in sorted order so the cost is at
most $1$. We show that there is no competitive algorithm for this problem.
We use this lower bound to answer several fundamental questions about packing.
Specifically, we prove the non-existence of competitive algorithms for various
online translational packing problems of convex polygons, among them strip
packing, bin packing and perimeter packing.

Joint work with: Anders Aamand, Lorenzo Beretta, Linda Kleist.
Document Actions