Tamal K. Dey, Joachim Giesen, Edgar A. Ramos, and Bardia Sadri

The distance function to surfaces in three dimensions plays a key role in many geometric modeling applications such as medial axis approximations, surface reconstructions, offset computations, feature extractions and others. In most cases, the distance function induced by the surface is approximated by a discrete distance function induced by a discrete sample of the surface. The critical points of the distance function determine the topology of the set inducing the function. However, no earlier theoretical result has linked the critical points of the distance to a sampling of geometric structures to their topological properties. We provide this link by showing that the critical points of the distance function induced by a discrete sample of a surface either lie very close to the surface or near its medial axis and this closeness is quantified with the sampling density. Based on this result, we provide a new flow-complex-based surface reconstruction algorithm that, given a tight ε-sampling of a surface, approximates the surface geometrically, both in Hausdorff distance and normals, and captures its topology.

Symposium on Computational Geometry (SoCG), 2005 [PDF] Journal version in the SoCG’05 special issue of International Journal of Computational Geometry and Applications (IJCGA) (2008) 18(1/2) 29-61 [PDF]