Late Summer School at ETH Zuerich

[Bernd Gaertner]

                             Late Summer School

                      ``Facets of the Polytope World'' 

                ETH Zuerich, Switzerland, September 13-16, 1999

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

                         Bernd Gaertner 
            Departement Informatik, ETH Zentrum, IFW 
                   CH-8092 Zuerich, Switzerland 

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

____________________
--------------------
Speakers and topics:               

---------------------------------------------------------------------------
Bernd Gaertner: ``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. 

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

-------------
The compgeom mailing lists: see
http://netlib.bell-labs.com/netlib/compgeom/readme.html
or send mail to compgeom-request at research.bell-labs.com with the line:
send readme
Now archived at http://uiuc.edu/~sariel/CG/compgeom/threads.html.