Extreme Points Under Random Noise

摘要

Given a point set P = {p_1,..., p_n} in the d-dimensional unit hyper-cube, we give upper bounds on the maximal expected number of extreme points when each point p_i is perturbed by small random noise chosen independently for each point from the same noise distribution Δ. Our results are parametrized by the variance of the noise distribution. For large variance we essentially consider the average case for distribution Δ while for variance 0 we consider the worst case. Hence our results give upper bounds on the number of extreme points where our input distributions range from average case to worst case. Our main contribution is a rather general lemma that can be used to obtain upper bounds on the expected number of extreme points for a large class of noise distributions. We then apply this lemma to obtain explicit bounds for random noise coming from the Gaussian normal distribution of variance σ~2 and the uniform distribution in a hypercube of side length ε. For these noise distributions we show upper bounds of O((1/σ)~d • log~(3/2.d-1)n) and O(((n log n)/ε)~(d/(d+1))), respectively. Besides its theoretical motivation our model is also motivated by the observation that in many applications of convex hull algorithms the input data is inherently noisy, e.g. when the data comes from physical measurement or imprecise arithmetic is used.