28549 articles – 22058 Notices  [english version]

inria-00438409, version 1

## The Effect of Noise on the Number of Extreme Points

Dominique Attali () a1, Olivier Devillers () b2, Xavier Goaoc () 3

N° RR-7134 (2009)

Résumé : Assume that Y is a noisy version of a point set X in convex position. How many vertices does the convex hull of Y have, that is, what is the number of extreme points of Y? We consider the case where X is an (epsilon,kappa)-sample of a sphere in Rd and the noise is random and uniform: Y is obtained by replacing each point x in X by a point chosen uniformly at random in some region R(x) of size delta around x. We give upper and lower bounds on the expected number of extreme points in Y when R(x) is a ball (in arbitrary dimension) or an axis-parallel square (in the plane). Our bounds depend on the size n of X and $\delta$, and are tight up to a polylogarithmic factor. These results naturally extend in various directions (more general point sets, other regions R(x)...). We also present experimental results, showing that our bounds for random noise provide good estimators of the behavior of snap-rounding, that is when Y is obtained by rounding each point of X to the nearest point on a grid of step delta.

• a –  CNRS
• b –  INRIA
• 1 :  Grenoble Images Parole Signal Automatique (GIPSA-lab)
• CNRS : UMR5216 – Université Joseph Fourier - Grenoble I – Université Pierre-Mendès-France - Grenoble II – Université Stendhal - Grenoble III – Institut Polytechnique de Grenoble - Grenoble Institute of Technology
• 2 :  GEOMETRICA (INRIA Sophia Antipolis / INRIA Saclay - Ile de France)
• INRIA
• 3 :  VEGAS (INRIA Lorraine - LORIA)
• INRIA – CNRS : UMR7503 – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine (INPL)
• Domaine : Informatique/Géométrie algorithmique
• Mots-clés : Complexity – Convex hull – Noisy data
• Référence interne : RR-7134

• inria-00438409, version 1
• oai:hal.inria.fr:inria-00438409
• Contributeur :
• Soumis le : Vendredi 4 Décembre 2009, 10:12:58
• Dernière modification le : Vendredi 4 Décembre 2009, 10:16:38