hide
Free keywords:
Computer Science, Computational Geometry, cs.CG
Abstract:
We consider offsets of a union of convex objects. We aim for a filtration, a
sequence of nested simplicial 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. The size of the filtration and the time complexity for computing it
are proportional to the size of the Voronoi diagram and its time complexity,
respectively. Our approach is inspired by alpha-complexes for point sets, but
requires more involved machinery and analysis primarily since Voronoi 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 a point
sample.
