Oberseminar

Konrad Deppert University of Hamburg

April 16, 2021, 13:00, zoom: https://uni-hamburg.zoom.us/j/94889228942

Title: Lower-Left Anchored Hyperrectangle Packing

Imagine the unit square U and n points that are placed in U. For every point p
and the origin, you have to draw a rectangle in U which has p as its lower-left left
corner and does not overlap with any other rectangle. How much area will you
be able to cover? This packing problem has been around for over half a century
and it has been conjectured that it is always possible to cover at least half of the
square. The conjecture is still open. About ten years ago, Dumitrescu and Tóth
showed that at least 9.1% of the square can always be filled.
We generalize the lower-left anchored rectangle packing problem to arbitrary dimensions
and try to carry over the 9.1%-result, which turns out to be very challenging.
Also, we analyze the special input configuration where the points have to
be in strictly increasing order.