|
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.
|
|