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

Date Speaker Title and abstract of the talk
Mo 27.03.2000 no colloquium today
Mo 03.04.2000 Prof. J.-R. Sack
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 non-convex 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

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 self-dual 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@kam-enterprise.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 r-hypergraph KG_r(S) has S as the vertex set, and an r-tuple (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})) >= n-2k+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 non-specialists 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 well-established 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 well-known 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.fu-berlin.de/inst/ag-ti/members/alt.en.html
alt@inf.fu-berlin.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 NP-hard for arbitrary numbers of polygons. (Joint work with Ferran Hurtado.)

Mo 29.05.2000 Prof. Thomas Erlebach
TIK Technische Informatik
D-ELEK, ETH
http://www.tik.ee.ethz.ch/~erlebach/
erlebach@tik.ee.ethz.ch
Edge-Disjoint Paths Problems in Specific Networks

Abstract: Edge-disjoint 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 edge-disjoint 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 row-column 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 edge-disjoint 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.uni-leipzig.de/cgip/
saupe@informatik.uni-leipzig.de
Fractal image compression: Review and state-of-the-art

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 post-processing. 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.uni-leipzig.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 2-D Xray Images

Abstract: In medical applications there is an increasing need for the acquisition and the automatic analysis of 3-D volume data. Since 1999 Siemens Medical Systems offers a product which provides a 3-D reconstruction option for standard Xray systems.

In this talk I will define the computer vision problems involved in the reconstruction of volumes from 2-D 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 3-D 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 free-form 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.math-inst.hu/~barany/
barany@math-inst.hu
0-1 polytopes with many facets

Abstract: An n-dimensional 0-1 polytope is, by definition, the convex hull of some vertices of the unit cube in R^n. We show that there are n-dimensional 0-1 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.

Previous colloquia:  WS 99/00SS 99WS 98/99SS 98WS 97/98SS 97
!!! Dieses Dokument stammt aus dem ETH Web-Archiv und wird nicht mehr gepflegt !!!
!!! This document is stored in the ETH Web archive and is no longer maintained !!!