[home] - [up]


Lectures and Colloquia during the semester



November 21, 2005

Freie Universität Berlin - Institut für Informatik
Takustraße 9
14195 Berlin
Room 005           - map -
Lecture - 14:15

Michel Pocchiola -École Normale Supérieure, Paris

Computing pseudotriangulations via coverings of the euclidean plane

Abstract: Algorithms that perform computations on sets of points in the plane frequently benefit from using the points to decompose the plane into simpler regions: triangulations, Voronoi diagrams, visibility maps, and Delaunay tesselations are good examples.

Decompositions called pseudo-triangulations or geodesic triangulations have been used in several visibility computations, in a number of kinetic data structures for collision detection among moving objects, or in an elegant proof that it is always possible to unfold a chain without self-intersection.

In this talk we show that a pseudotriangulation of a collection of n pairwise disjoint bounded closed 2-dimensional convex sets in the euclidean plane is computable in O(n log n) time using only its chirotope. The method relies on an extension of the theory of pseudotriangulations and visibility complexes to branched coverings of the euclidean plane, and on several new combinatorial properties of topological cross-sections of visibility complexes. (Joint work with Luc Habert.)


Colloquium - 16:00

Eyal Ackerman - Technion-Israel Institute of Technology, Haifa

On the maximum number of edges in k-quasi-planar graphs

Abstract: A topological graph is called k-quasi-planar, if it does not contain k pairwise crossing edges. It is conjectured that for every fixed k the maximum number of edges in a k-quasi-planar graph on n vertices is O(n). We provide, for the first time, an affirmative answer to the case k=4. We also give the simplest proof and the best upper bound known, for the maximum number of edges in 3-quasi-planar graphs on n vertices. Moreover, we show a tight upper bound for 3-quasi-planar graphs in which every pair of edges meet at most once.

Joint work with Gabor Tardos.


[home] - [up] - [top]