Si Y est une version bruitée d’un ensemble de points X en position convexe, quelle est la taille de l’enveloppe convexe de Y, c’est à dire quel est le nombre de points extrêmes de Y? Nous considérons le cas où X est un (ε,κ)-échantillon de la sphère de Rd et où le bruit est aléatoire et uniforme: Y est obtenu en remplaçant chaque point x∈ X par un point choisi aléatoirement dans une région P(x) de taille δ au voisinage de x. Nous donnons des bornes inférieures et supérieures sur l’espérance du nombre de points extrêmes de Y lorsque P(x) est une boule (en toute dimension) ou un carré (dans le plan). Nos bornes dépendent de n la taille de X et de δ. L’écart entre les bornes supérieurs et inférieures est réduit à un facteur polylogarithmique. Ces résultats peuvent s’étendre dans diverses directions (ensemble de points plus généraux, autre formes pour P(x)…). Nous présentons également des résultats expérimentaux montrant que nos bornes pour un bruit aléatoire donnent une bonne estimation du comportement de l’arrondi de points sur une grille. Dans ce cas Y est obtenu en arrondissant chaque point de X au plus proche sommet d’une grille de pas δ.
Travail réalisé en collaboration avec Dominique Attali et Xavier Goaoc.
Plus d’informations sur http://hal.inria.fr/inria-00438409/.
This document was translated from LATEX by HEVEA.