Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
locations | Term schedule | history
predoc-courses | schools | block-courses | workshops

Monday Lecture and Colloquium

Monday, October 19, 2009

Freie Universität Berlin
Institut für Informatik
Takustrasse 9
14195 Berlin
room MA 005

Lecture - 14:15

Günter Rote - FU Berlin

Counting Polycubes

A polycube (a high-dimensional analog of a polyomino) is a connected set of lattice cubes. We show how to obtain explicit formulas for the number of polycubes for those cases where the number d of dimensions that are spanned by a polycube is not much smaller than n, the number of cubes. In particular, for d = n-1 (the largest possible value of d), d = n-2, and d = n-3, we obtain formulas of the form $2^n n^{2n-d-1}$ times a polynomial factor in n.
These formulas are based on a correspondence with directed spanning trees and on an inclusion-exclusion principle, counting certain "substructures" that may appear in polcubes. Such formulas have been proposed without rigorous proofs in the statistical-physics literature.

Colloquium - 16:00

Fabian Stehn FU Berlin

From Registrations to Non-uniform Geometric Matchings, a Geometric Problem with Neurosurgical Applications

Nowadays most neurosurgical operations are supported by medical navigation systems. The purpose of these systems is to provide the surgeon with additional information during the surgery, like a projection of the used instrument into a 3D model of the relevant area of the patient. These models are computed beforehand from computer tomography (CT) or magnetic resonance tomography (MRT) scans of the patient. Once the rigid transformation that correctly maps the operation field into the model space is known, this problem can be solved easily. Thus, a central ingredient of a medical navigation system is a strategy to compute these transformation. In this talk I present the afore mentioned motivating application background. Then, the problem of geometric registrations will be introduced and how they are usually reduced to geometric matching problems. I'll present a novel concept of so-called non-uniform geometric matchings which generalize the geometric matching concept by allowing to compute a set of transformations that locally match regions of interest.

Letzte Aktualisierung: 09.10.2009