Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, March 05, 2020, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Nadja Seiferth (FU Berlin)
We consider the problem of finding in three dimensions a minimum volume axis-parallel box into which a given set of unit size disks can be packed under translations. The problem is neither known to be NP-hard nor to be in NP. We give a constant-factor approximation algorithm based on reduction to finding a shortest Hamiltonian path in a weighted graph. As a byproduct, we can show that there is no finite size container into which all unit disks can be packed simultaneously. This is joint work with Helmut Alt, Otfried Cheong, and Ji-won Park.
Automatic MiSe System Software Version 1.4803M | admin login