November 12 , 2007
Freie Universität Berlin
Institut für Informatik
Takustr. 9,
room 005
Lecture - 14:15
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
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.