#
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