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, May 17, 2010

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

Lecture - 14:15

Vera Sacristan - Barcelona

Reconfiguration of cube lattice modular robots

I will present some recent results and ongoing research on self-reconfiguration of modular robots composed of cubical units (atoms) arranged in a lattice configuration and capable of performing four basic actions: expand and contract, as well as attach and detach from neighbors.

This work includes centralized and distributed solutions, as well as massive parallelization of the robot moves. The proposed algorithms are in-place, guarantee the connection of the reconfiguration space and improve the previously known algorithms.

This is partially joint work with O. Aichholzer, G. Aloupis, S. Collette, M. Damian, E. Demaine, R. Flatland, T. Hackl, S. Langerman, V. Pinciu, J. O’Rourke, S. Ramaswami, B. Vogtenhuber, R. Wallner and S. Wuhrer.

Colloquium - 16:00

Richard Gardner - Western Washington University

Reconstruction in Geometric Tomography

Geometric tomography is the area of mathematics concerned with the retrieval of information about a geometric object from data about its orthogonal projections onto lines or planes or its intersections with lines or planes. In recent years, a number of algorithms have been developed for the purpose of reconstructing convex bodies from data of this sort. Examples are parallel and point X-rays, width or brightness functions, and support functions. In each case the algorithm takes as input a finite number of noisy (that is, corrupted by error) measurements and outputs a convex polytope that approximates the unknown convex body. The algorithms have all been proved to be strongly consistent, meaning that under suitable conditions, the Hausdorff distance from the output convex polytope to the unknown body converges, almost surely, to zero as the number of measurements increases. In some cases rates of convergence have also been obtained by applying the theory of empirical processes.

The talk will survey these results, and briefly mention also a very recent one concerning reconstruction from covariograms, functions giving the volume of the intersection of a convex body with its translates. This reconstruction problem is closely related to the Phase Retrieval Problem for characteristic functions of convex bodies.

The earliest algorithm to be discussed was proposed by electrical engineers in 1990, without proof of convergence. The mathematical methods involve convex geometry and probability, but the talk is intended to be accessible to a general audience. The algorithms have been implemented and pictures of typical computer reconstructions will be presented.

Letzte Aktualisierung: 10.05.2010