The goal of this school is to introduce a number of basic concepts in discrete geometry to students of different levels by means of lectures and exercises. Each of the three speakers will cover a full day (titles and abstracts below), and one more day (Wednesday 12) is reserved for a hike in the beautiful mountains of Switzerland.

There will be no assumptions beyond basic Linear Algebra and a familiarity with mathematical concepts in general.

There is no participation fee. We arrange for student housing in single or double rooms, expecting arrival Sunday night and departure Friday morning. The rates are CHF 80,- (single) resp. CHF 60,- (double) for the whole period. We provide a certificate of participation (with an exam, if that is requested). The school will be announced as a regular course with credit at the ETH.

The number of participants is limited. An application should be sent as early as possible, but definitely before July 15 to the address below. It should include a short Curriculum Vitae and indication whether accommodation as offered above is needed (in which case early registration is highly recommended).

For further information: Tel ++41 1 632 73 92, Fax ++41 1 632 11 72, email gaertner@inf.ethz.ch or richter@inf.ethz.ch

Für ETH Studierende: Der Blockkurs 37-440 wird mit 3 Krediteinheiten verrechnet. Mündliche Prüfung nach Vereinbarung. Anmeldung per e-mail bei Bernd Gärtner (gaertner@inf.ethz.ch).

Speakers and topics:

Bernd Gärtner: ``Randomization and Abstraction in geometric optimization''

Many popular geometric optimization problems (smallest enclosing ball of points, distance between polytopes,...) can be regarded as instances of a simple abstract class known as `LP-type problems'. I will introduce this general framework, describe randomized algorithms for solving all problems in the class, and derive bounds for their expected performance. Among other upper and lower bounds, I will review the currently best theoretical bound for solving the special geometric optimization problem of linear programming in the unit cost model.

Jürgen Richter-Gebert: ``Polytopes in small dimensions''

Already in dimensions three and four, polytopes show a large variety of interesting properties, surprising effects and widely open research problems. We will try to explore some of the most interesting parts of these stories. Among them are
- the relation of Spiderwebs, a photograph of the Golden Gate Bridge and polytopes,
- how one can cage eggs and potatoes in a tight way by three dimensional polytopes,
- why four dimensional polytopes behave as bad as arbitrary polynomials,
- and how difficult it is to embed a polytope in a finite quantitized universe

Emo Welzl: ``Halving Point Sets - The Inner Structure of Point Sets''

The convex hull of a point set gives a convex polytope, which - in some sense - describes the outer structure of the point set. Here we plan to investigate the inner structure, along questions like:

Given 2n points in the plane, no three on a line.
How many pairs of points can be connected by a halving
line, i.e., a line halving the remaining 2n-2 points?

So for four points, there are at most three such pairs? Even this innocent looking question in the plane is far from being solved (the answer is known for up to 12 points), not to mention the higher dimensional counterparts. We demonstrate several techniques from discrete geometry applied to these questions, we point out sometimes surprising connections to other problems, and we exhibit a number of computational problems, where these questions arise.