# Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
|
locations | Term schedule | history
|

# 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

### Counting Polycubes

Abstract:
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

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

Abstract:
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