CSc 82000: Packing and Covering: Theory and Algorithms


Graduate Course in Computer Science and Mathematics
Offered by János Pach
Fall term, 2000, Wednesdays 4:15-6:15 pm


How many objects of a given shape and size can be packed into a large box of fixed volume? Given a set system, what is the smallest number of elements with the property that every member of the system contains at least one of them? These questions raised by Gauss, Minkowski, Hilbert, Helly, Konig, and many others turned out to be centrally important in number theory, coding theory, discrepancy theory, mathematical statistics, combinatorial optimization, and many areas
of computer science from bin packing to robotics. This course offers an introduction to this rapidly developing field, where combinatorial and probabilistic (counting) methods play a crucial role.
Some familiarity with multivariate calculus and probability theory is required.

Topics: Geometry of numbers, Approximation of convex sets by polygons, Packing and covering with congruent convex discs, Lattice packing and lattice covering, The method of cell decomposition, Methods of Blichfeldt and Rogers, Efficient random arrangements, Epsilon-nets and transversals of hypergraphs, Geometric discrepancy, Bin packing.

Textbook: J. Pach and P. Agarwal: Combinatorial Geometry, Wiley, New York, 1995.