[home] - [up]


Lectures and Colloquia during the semester



January 30, 2006

Technische Universität Berlin
Straße des 17. Juni 136
10623 Berlin
Math building - Room MA 041           - map -
Lecture - 14:15

Emo Welzl - ETH Zürich

On the number of crossing-free configurations on planar point sets

Abstract: Given a finite set P of points in the plane, a geometric graph on P has P as its vertex set and the edges are realized by straight segments. We consider crossing-free geometric graphs of various types, e.g. triangulations, perfect matchings or spanning cylces, and we are interested in the number of such graphs that exist on P.

If P is in convex position, then these numbers are determined by the number of points in P (and invoke the Catalan Numbers). Here our goal is to derive bounds on how many such crossing-free graphs (of various types) a set of n points can allow at most. All bounds are of the form c^n and the crux of the matter is to get c as small as possible.

This reports on joint work with Micha Sharir.


Colloquium - 16:00

Sarah J. Kappes - Technische Universität Berlin

Non-Generic Orthogonal Surfaces

Abstract: Generic orthogonal surfaces are in relation with Scarf-Complexes and are rather well understood. In the non-generic case, it is much harder to ensure that the surface has a nice combinatorial structure.

We examine some properties of orthogonal surfaces that are less restrictive than genericity but still allow us to draw some conclusions.

For non-degenerate and rigid orthogonal surfaces, we present some results (and some more open problems) concerning the poset of characteristic points.


[home] - [up] - [top]