Monday, May 17, 2010
Freie Universität Berlin
Institut für Informatik
Takustrasse 9
14195 Berlin
MA 005
Lecture - 14:15
Abstract:
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
Abstract:
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.