A simple algorithm for homeomorphic surface reconstruction

The problem of computing a piecewise linear approximation to a surface from a set of sample points is important in solid modeling, computer graphics and computer vision. A recent algorithm(1) using the Voronoi diagram of the sample points gave a guarantee on the distance of the output surface from the original sampled surface assuming that the sample was sufficiently dense. We give a similar algorithm, simplifying the computation and the proof of the geometric guarantee. In addition, we guarantee that our output surface is homeomorphic to the original surface; to our knowledge this is the first such topological guarantee for this problem.