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 σ² and the uniform distribution in a hypercube of side length &epsilon. 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.@eng bibo_authorlist: - foaf_Person: foaf_givenName: Valentina foaf_name: Damerow, Valentina foaf_surname: Damerow - foaf_Person: foaf_givenName: Christian foaf_name: Sohler, Christian foaf_surname: Sohler bibo_doi: 10.1007/978-3-540-30140-0_25 dct_date: 2004^xs_gYear dct_isPartOf: - http://id.crossref.org/issn/0302-9743 - http://id.crossref.org/issn/1611-3349 - http://id.crossref.org/issn/9783540230250 - http://id.crossref.org/issn/9783540301400 dct_language: eng dct_title: Extreme Points Under Random Noise@ ...