Medial Axis Approximation and Unstable Flow Complex




Edgar A. Ramos, Joachim Giesen, and Bardia Sadri

The medial axis of a shape is known to carry a lot of information about it. In particular a recent result of Lieutier establishes that every bounded open subset of Rn has the same homotopy type as its medial axis. In this paper we provide an algorithm that, given a sufficiently dense but not necessarily uniform sample from the surface of a shape with smooth boundary, computes a core for its medial axis approximation, in form of a piecewise linear cell complex, that captures the topology of the medial axis of the shape. We also provide a natural method to freely augment this core in order to enhance it geometrically all the while maintaining its topological guarantees. The definition of the core and its extension method are based on the steepest ascent flow induced by the distance function to the sample. We also provide a geometric guarantee on the closeness of the core and the actual medial axis.

Symposium on Computational Geometry (SoCG), 2006. [PDF]
Journal version in the SoCG’06 special issue of International Journal of Computational Geometry and Applications (IJCGA). Volume 18, Issue 6, 2009 [PDF]
SoCG presentation slides [
PDF]