Reconstructing shapes with guarantees by unions of convex sets
Dominique Attali, André Lieutier · 2010
A simple way to reconstruct a shape A from a sample P is to output an r-offset P + r B, where B = {x ∈ RN x ≤ 1} 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 ⊂ RN, besides the unit Euclidean ball B, for which P + rC reconstructs the topology of A. This class of convex sets includes in particular N-dimensional cubes in RN. 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.