Notice

 
Abstract
Packing problems arise in many applications, such as manufacturing and scheduling, and are also interesting as purely mathematical questions such as Kepler’s Conjecture. As a case study, we consider a packing problem that appears rather easy: given a collection of coins (circular disks), how can we pack them “on a shelf,” that is, such that each disk touches the x-axis from above and such that no two coins overlap, and minimize the width of the shelf?
We will see that in its most general form, this problem is surprisingly hard – finding a polynomial-time algorithm would imply P= NP.   On the other hand, we will see that a special case, where the size of the coins doesn’t vary too much, can be solved easily in O(n log n) time.   For the general case, we give an O(n log n) algorithm that guarantees a shelf that is at most 33% wider than the optimal shelf.
Joint work with Helmut Alt, Kevin Buchin, Steven Chaplick, Philipp Kindermann, Christian Knauer, and Fabian Stehn.
 
Short Bio
Otfried Cheong is an ACM Distinguished Scientist and one of the authors of the standard textbook on Computational Geometry. He has been at KAIST’s School of Computing since 2005, after holding positions in Utrecht, Postech, HKUST, and TU Eindhoven.