Smoothed number of extreme points under uniform noise

Abstract

We analyze the maximal expected number of extreme points of a point set P in Rd that is slightly perturbed by random noise. We assume that each point in P is uniformly distributed in an axis-aligned hypercube of side length 2r entered in the unit hypercube (the enter of the hypercube an be regarded as the point position without noise). Our model is motivated by the fact that in many applications the input data is inherently noisy, e.g. when the data comes from physical measurement or imprecise arithmetic is used. For this input distribution we derive an upper bound of O((n . log n/e) 1-1/(d+1)) on the number of extreme points of P.