Two approaches for polyhedral reconstruction of 3D objects of arbitrary genus

This paper addresses the problem of constructing a polyhedral approximation of a 3D object, given by a set of scattered points from the object's surface. Two solutions of this problem are presented. Both methods use the Delaunay triangulation as an initial neighbourhood graph. The first approach is based on Boissonnat's strategy to remove tetrahedra from the hull of the graph according to a cost function. Our algorithm extends Boissonnat's work to objects of arbitrary genus and offers an automatic termination procedure. The second method defines a new approach to approximate the minimal spanning Voronoi tree which was introduced by O'Rourke et al. Here, in the first step, tetrahedra are grouped into polyhedra and in a second step they are classified to belong either to the polyhedral reconstruction or not.