Reconstruction certifiée de formes à l’aide d’unions de convexes

Dominique Attali (Gipsa-Lab, Grenoble)

Une façon simple de reconstruire une forme A ⊂ ℝ^N à partir d’un échantillon P consiste à retourner en sortie un r-offset de l’échantillon P+rB, où B = {x ∈ ℝ^N ∣ ||x|| ≤ 1 } désigne la boule euclidienne unité centrée en l’origine. Récemment, il a été prouvé que la sortie P + r B possède le même type d’homotopie que la forme A, pour un échantillon P de A suffisamment dense et pour une valeur convenable du paramètre r [1,2]. Dans cet exposé, nous étendons ce résultat et présentons une classe de convexes C ⊂ ℝ^N, tels que P + rC reconstruisent correctement la topologie de A. Cette classe de convexes, en plus de la boule euclidienne B inclut les cubes de dimension N de ℝ^N.

Travail réalisé en collaboration avec André Lieutier.

1. P. Niyogi, S. Smale, and S. Weinberger. Finding the Homology of Submanifolds with High Confidence from Random Samples. Discrete Computational Geometry, 39(1-3):419–441, 2008.
2. F. Chazal and A. Lieutier. Smooth Manifold Reconstruction from Noisy and Non Uniform Approximation with Guarantees. Computational Geometry: Theory and Applications, 40:156–170, 2008.

This document was translated from L^AT_EX by H^EV^EA.