Reconstructing Shapes with Guarantees by Unions of Convex Sets

International audienceA simple way to reconstruct a shape A from a sample P is to output an offset P + r B, where B designates the unit Euclidean ball centered at the origin. Recently, it has been proved that the output P + r B is homotopy equivalent to the shape A, for a dense enough sample P of A and for a suitable value of the parameter r. In this paper, we extend this result and find convex sets C, besides the unit Euclidean ball B, for which P + r C reconstructs the topology of A. This class of convex sets includes in particular N-dimensional cubes. We proceed in two steps. First, we establish the result when P is an offset of A. Building on this first result, we then consider the case when P is a finite noisy sample of A