Inferring the Geometry of Convex Shapes from Their Gauss Digitization

This paper studies how well we can infer the geometry of a (smooth or not) convex shape X from the convex hull Yh of its Gauss digitization with a given gridstep h. Without smoothness constraint on X, we first present results concerning the proximity of facet normal vectors to the shape normal vectors, as well as a relation between the number of lattice points just above a facet and its area. Then, further results can be obtained when X is smooth, that are valid in arbitrary dimension d. More precisely, we show that the boundary of Yh is Hausdorff-close to the boundary of X with distance less than $\sqrt{d}h$, and that the vertices of Yh are even much closer (some $O(h^{\frac{2d}{d+1}})$). Our main result states that the geometric normal vectors to the facets of Yh tend to the smooth shape normals with a speed $O(h^{\frac{1}{2}}), and the bound is tight. Finally we compare experimentally the performances of several normal estimators built upon the normal vectors to the facets of Yh with state-of-the-art estimators. We also perform statistical analyses over the facets of digitized convex hulls, like their area, diameter or width as a function of the digitization gridstep. Both our new theoretical properties and our numerical experiments confirm that the convex hull of a digitized shape provide relevant information on the geometry of the underlying Euclidean convex shape, and can be used to construct fast and accurate geometric estimators.