Speaker: Doron Shaharabani (TAU

Title: The Offset Filtration of Convex Objects

Abstract:
---------
We consider offsets of a union of convex objects. We aim for a filtration, a sequence of 
nested cell complexes, that captures the topological evolution of the offsets for increasing 
radii. We describe methods to compute a filtration based on the Voronoi partition with respect 
to the given convex objects.We prove that, in two and three dimensions, the size of the 
filtration is proportional to the size of the Voronoi diagram.Our algorithm runs in 
$\Theta(n \log{n})$ in the $2$-dimensional case and in expected time $O(n^{3 + \eps})$, 
for any $\eps > 0$, in the $3$-dimensional case.  Our approach is inspired by alpha-complexes 
for point sets, but requires more involved machinery and analysis primarily sinceVoronoi 
regions of general convex objects do not form a good cover. 

We show by experiments that our approach results in a similarly fast and topologically more 
stable method for computing a filtration compared to approximating the input by point samples.

Joint work with Dan Halperin and Michael Kerber.