Herr Dr. Joachim Giesen,

        Fachbereich Informatik,

        ETH Zürich

hält am  

        Donnerstag, den 8.12.2005 um 16 Uhr s.t.

        im Raum KI/II (über dem Labsaal)

einen Vortrag mit dem Titel

        Rekonstruktionsprobleme

Zusammenfassung:

Mein Vortrag besteht aus zwei Teilen. In jedem Teil werde ich jeweils ein Rekonstruktionsproblem behandeln. Rekonstruktionsprobleme bieten einen theoretischen Rahmen, um Algorithmen zu validieren bzw. zu vergleichen.

Im ersten Teil diskutiere ich das Problem, eine Fläche im dreidimensionalen Raum aus einer endlichen Teilmenge (Punktwolke) zu rekonstruieren. Flächenrekonstruktion ist ein mächtiges Modellierungswerkzeug, das es auf einfache Art und Weise erlaubt, digitale 3D-Modelle zu erzeugen. Dazu tastet man ein physikalisches Objekt ab, um eine Punktwolke seiner Oberfläche zu erhalten. Ein Flächenrekonstruktionsalgorithmus erzeugt dann aus der Punktwolke ein kontinuierliches Flächenmodell, z.B. ein Dreiecksnetz. Ich werde eine neue von uns entwickelte Datenstruktur und einen darauf basierenden Algorithmus zur Lösung des Flächenrekonstruktionsproblems vorstellen und analysieren. Die Datenstruktur, ein polyedrischer Komplex, erlaubt interessante Einblicke in verwandte Datenstrukturen, wie die Delaunay Triangulierung und das Voronoi Diagramm der Punktwolke, und hat auch Anwendungen in der bio-geometrischen Modellierung.

Im zweiten Teil widme ich mich dem Problem, eine vorgegebene aber zufällig verrauschte Struktur in einem Graphen, z.B. eine Partitionierung seiner Knotenmenge in Cliquen, zu rekonstruieren. Als Anwendung analysiere ich einen Algorithmus zur Lösung eines typischen Marktforschungsproblems. Eine Population von Kunden wird nach ihren Produktpräferenzen befragt, indem jeder Kunde nur sehr wenige Produktpaare vergleichen muss. Aus den paarweisen Produktvergleichen aller Kunden sollen dann fuer die Population typische Produktrangordnungen bestimmt werden.