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

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.

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.

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.

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

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.

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.

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.

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.

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.