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
partners


Monday Lecture and Colloquium


November 12 , 2007

Freie Universität Berlin
Institut für Informatik
Takustr. 9,
room 005

Lecture - 14:15

Herbert Edelsbrunner - Arts and Sciences Professor of Computer Science and
Mathematics, Duke University, and Visiting Professor at the Berlin Mathematical School

The power cell algorithm for local homology vineyards

Abstract:
We study the reconstruction of a stratified space from a possibly noisy point
sample. Specifically, we use the vineyard of the distance function restricted to a
1-parameter family of neighborhoods of a point to assess the local homology of the
stratified space. We prove the correctness of the assessment under the assumption
of a sufficiently dense sample.  We also give an algorithm that constructs the
vineyard in time at most cubic in the size of the Delaunay triangulation of the
point sample.
This is work with Paul Bendich, David Cohen-Steiner John Harer, and Dmitriy Morozov.




Colloquium - 16:00

Hans Raj Tiwary, Universität des Saarlandes


How not to Enumerate Vertices of a Polytope

Abstract:
A polytope in R^d can be represented either as Convex Hull of a finite
number of points or as intersection of a finite number of halfspaces. If
redundancies are not allowed then these representations are unique for
every polytope. A very fundamental problem in algorithmic polytope
theory is to convert one representation to the other. In this talk I
will discuss different approaches to this problem and why they don't
work. I will also talk about an isomorphism problem related to polytopes
that has interesting connections with the problem of representation
conversion.



Letzte Aktualisierung: 05.11.2007