Colloquium on Combinatorics, Geometry and Computation
Program for SS 2000, as of May 8 2000
If not otherwise noted:
Time: Monday's 14:15  16:00
Room: IFW A 32
Please send questions and comments to Bernt
Schiele.
Date 
Speaker 
Title and abstract of the talk 
Mo 27.03.2000 
no colloquium today 

Mo 03.04.2000 
Prof. J.R. Sack Carleton University, Ottawa, Canada,
http://www.scs.carleton.ca/~sack
sack@scs.carleton.ca

Shortest Path Algorithms (practical and theoretical)
Abstract:
Shortest path problems are among the fundamental problems studied
in computational geometry and other areas such as graph algorithms,
geographical information systems (GIS) and robotics.
Let $s$ and $t$ be two vertices on a given possibly nonconvex
polyhedron $\cal P$,
in $\Re^3$, consisting of $n$ triangular faces on its boundary,
each face has an associated positive weight.
Weights may represent e.g. possible traveling speeds.
A {\it weighted shortest path} $\Pi(s,t)$ between $s$ and $t$ is defined to be
a path with minimum cost among all possible paths joining $s$ and $t$ that
lie on the surface of ${\cal P}$. The {\it cost} of the path is the sum
of the lengths of all segments multiplied by the corresponding face weight.
Finding minimum cost (weighted) paths is typically hard or very time intensive.
Thus approximation algorithms are required and usually
appropriate as e.g. terrains are approximations of reality anyway.
In this talk we discuss several algorithms (schemes)
to compute an approximated weighted shortest path
$\Pi'(s,t)$ between two points $s$ and $t$ on the surface of a
polyhedron ${\cal P}$. 
Mo 10.04.2000 
no colloquium today 
Sechselaeuten 
Mo 17.04.2000 
Prof. Jon Lee
Univ. of Kentucky, currently visiting
Center for Operations Research and Econometrics Universite
Catholique de Louvain, Belgium
http://www.ms.uky.edu/~jlee/
lee@core.ucl.ac.be

On Dyadic Oriented Matroids
Abstract:
Matroids were introduced by Whitney in the 1930's as a
common
generalization of (i) linear dependence and (ii) the incidence
relations
of cycles in graphs. They are of central importance in combinatorial
optimization and coding theory. Oriented matroids were introduced by
Bland
and Las Vergnas in the 1970's as a means of abstracting the additional
structure related to (i) an ordering of the field when the matroid
comes
from linear dependence and (ii) the incidence relations of cycles in
directed graphs. Oriented matroids are intimately related to the
studies
of ordering of points, linear programming and polyhedra, and
convexity.
A fundamental question for a class of matroids is to describe where
they
might come from. For example, the following are well known: (i) every
(oriented) matroid that comes from cycles of a (directed) graph can
also
be seen to come from linear dependence over every field; (ii) every
matroid that comes from linear dependence over the 2 and 3 element
fields
can also be seen to come from linear dependence over every field.
Such results can be seen as describing different ways of encoding
dependence information.
In this talk, *I will assume no prior knowledge of matroids*. I will
develop the basic facts, expanding on what I have summarized above. In
particular, I will explain how several theorems concerning
representations
can be easily seen to follow from a selfdual characterization of
representations due to Bland and myself. Armed with this, we will see
an
elementary construction for orienting matroids that come from linear
dependence over the 3 and 5 element fields. Finally, I'll describe a
characterization, due to Scobee and myself, of this class of oriented
matroids as a special subclass of oriented matroids that come from the
rationals. We can view this result as providing a compact means of
encoding convexity information for certain sets of rational points. 
Mo 24.04.2000 
no colloquium today 
Ostern 
Mo 01.05.2000 
no colloquium today 
Tag der Arbeit 
Mo 08.05.2000 
Prof. Jiri Matousek
Charles University, Prague, Czech Republic
http://www.ms.mff.cuni.cz/~matousek
matousek@kamenterprise.ms.mff.cuni.cz

On the chromatic number of Kneser hypergraphs
Abstract:
Let S be a system of subsets of a finite set X. The
Kneser rhypergraph KG_r(S) has S as the vertex set,
and an rtuple (S_1,S_2,...,S_r) of sets in S forms
an edge if S_i intersected S_j is empty for all i < =j.
Kneser conjectured in 1955 that the chromatic number
chi(KG_2({[n] choose k})) >= n2k+2.
This was proved in 1978 by Lovasz as
one of the earliest and most spectacular applications of
topological methods in combinatorics.
Further proofs and extensions were obtained e.g. by
Barany, Schrijver, Walker, Alon, Frankl, Lovasz,
Do{\lsoft}nikov, Sarkaria, and Kriz.
In the talk, we consider a lower
bound for the chromatic number of KG_r(S) for an arbitrary
set system S due to Kriz from 1992
(for r=2, the result was obatined earlier by Dol'nikov
in 1988). We explain the statement and outline a proof;
the basic approach is similar to that
of Kriz, but our proof is simpler and
more accessible to nonspecialists in topology.
Time permitting, we will also discuss
other aspects of topological proofs
of the Kneser conjecture and related results will be
discussed.

Mo 15.05.2000 
Dr. Bernd Gärtner
ETH Zürich
http://www.inf.ethz.ch/personal/gaertner/
gaertner@inf.ethz.ch

Random Sampling and the Simplex Method: Combining Two Worlds
Abstract:
The random sampling paradigm is wellestablished in computational
geometry. Algorithms following this paradigm are often surprisingly
simple but at the same time provably efficient for very broad classes
of problems. However, when applied to concrete problems, like for
example linear programming, these algorithms have a reputation of
not being competitive with fast heuristics employed in practice.
I will present one particular random sampling technique which
combines provable with practical efficiency. Specialized to
linear programming, this technique implements a variant of
the wellknown multiple pricing heuristic for the simplex
method. Even in this special case, the analysis crucially
involves the generalized linear programming framework in
which the random sampling scheme efficiently works.

Mo 22.05.2000 
Prof. Helmut Alt
Institut für Informatik
Freie Universität Berlin
http://www.inf.fuberlin.de/inst/agti/members/alt.en.html
alt@inf.fuberlin.de

Packing Convex Polygons into Rectangular Boxes
Abstract: We will consider packing several convex polygons into minimum size rectangles.
For this purpose the polygons may
be moved either by translations only, or by combinations of translations
and rotations. We also will consider both cases, that the polygons may
overlap when being packed or that they must be disjoint. The {\em size} of a
rectangle to be minimized can either be its area or its perimeter.
In the case of overlapping packing very efficient algorithms can be found
even for an arbitrary number of polygons. For disjoint packing we will consider
packing two polygons. The problem is known to be NPhard for arbitrary numbers
of polygons. (Joint work with Ferran Hurtado.)

Mo 29.05.2000 
Prof. Thomas Erlebach
TIK Technische Informatik
DELEK, ETH
http://www.tik.ee.ethz.ch/~erlebach/
erlebach@tik.ee.ethz.ch 
EdgeDisjoint Paths Problems in Specific Networks
Abstract: Edgedisjoint paths problems have many
applications, for example in communication networks with bandwidth
reservation. Given a set of paths or connection requests in a network,
the goal is to select a subset of edgedisjoint paths with maximum
cardinality or maximum weight. We present algorithmic techniques that
lead to approximation algorithms with constant approximation ratio in
various specific network topologies, e.g., trees, trees of rings, and
meshes with rowcolumn routing. These techniques are either based on
simple greedy strategies or on linear programming and deterministic
rounding (using a path coloring subroutine). We also discuss the
relationship of the edgedisjoint paths problem to the independent set
problem and show how the approximation results can be generalized.

Mo 05.06.2000 
Prof. Dietmar Saupe
Institut für Informatik
Universität Leipzig
http://www.informatik.unileipzig.de/cgip/
saupe@informatik.unileipzig.de

Fractal image compression: Review and stateoftheart
Abstract: Before we address the main topic of the talk we
will give a short overview of the ongoing work in some of our computer
graphics and image processing group projects at the Institute of
Computer Science at the university of Leipzig. The basic idea of
fractal image compression was first conceived and implemented in 1989
by Arnaud Jacquin and Michael Barnsley. For a given image f the
fractal encoder constructs a contractive affine operator T, such that
its unique fixed point f* is close to the given image f. At the
decoder an iteration of T produces a reconstruction of the fixed point
f* due the Banach's fixed point theorem. After now 10 years of
research it seems as if the scientific work is nearly complete. Many
subproblems were dealt with, which uncovered close relations to other
compression methods (wavelets, vector quantization, DCT). We will
discuss contributions to the complexity reduction of the encoding,
adaptive image partitonings, improvement of the code by local search
and postprocessing. Finally, we comment on the pros and cons with
respect to other image compression methods. Details, an extensive
bibliography, some software, demos und papers are in
www.informatik.unileipzig.de/cgip/projects/fic.html.

Mo 12.06.2000 
no colloquium today 
Pfingsten 
Mo 19.06.2000 
Dr. Joachim Hornegger
AXET 1, Siemens Medical Systems, Germany
http://www.hornegger.de
joachim@hornegger.de

Robust Reconstruction of Volume Data from 2D Xray Images
Abstract: In medical applications there is an increasing
need for the acquisition and the automatic analysis of 3D volume
data. Since 1999 Siemens Medical Systems offers a product which
provides a 3D reconstruction option for standard Xray systems.
In this talk I will define the computer vision problems involved in
the reconstruction of volumes from 2D Xray images, and I will address
the problem of designing robust computer vision systems. From an
engineering point of view there are many ways to approach 3D
reconstruction: We can choose different parameterizations of our
models, we can apply various optimization algorithms to tackle search
problems, and there is no standard procedure to select appropriate
sample data. An obvious issue during the design of such a system is
the judgment and comparison of different options. Medical
applications do not ask for any solution to the problem but for the
best one. There is a need to introduce and to apply general concepts
which provide the required framework for system design. Examples in
my talk will discuss recent research results on fair parameterization,
the propagation of covariance matrices, and the application resampling
methods.

Mo 26.06.2000 
Prof. Harmut Prautzsch
Universität Karlsruhe
http://i33www.ira.uka.de/englisch/eindex.htm
prau@ira.uka.de

Smooth freeform surfaces
Abstract:
Theoretically and in principle it is well understood
how to build arbitrary smooth surfaces. However,
practically this is a challenging problem because
of geometrical, numerical and fairness constraints.
These difficulties will be explained and solutions
will be discussed that are simple to implement and
are based on piecewise polynomial surfaces
with control nets. 
Mo 03.07.2000 
Prof. Imre Barany
Mathematical Institute of
the Hungarian Academy of Sciences
http://www.mathinst.hu/~barany/
barany@mathinst.hu

01 polytopes with many facets
Abstract:
An ndimensional 01 polytope is, by definition, the convex
hull of some vertices of the unit cube in R^n. We show that there are
ndimensional 01 polytopes with superexponentially many facets. This
answers a question by Komei Fukuda and Gunter Ziegler. The construction
giving this bound is random. This is joint work with Attila Por. 
