Extreme Points Under Random Noise
Damerow, Valentina
Sohler, Christian
Given a point set P in the d-dimensional unit hypercube, we give upper bounds on the maximal expected number of extreme points when each point 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.<br>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.
2004
info:eu-repo/semantics/conferenceObject
doc-type:conferenceObject
text
https://ris.uni-paderborn.de/record/18778
Damerow V, Sohler C. Extreme Points Under Random Noise. In: <i>Proceedings of the 12th European Symposium on Algorithms (ESA’04)</i>. Berlin, Heidelberg; 2004. doi:<a href="https://doi.org/10.1007/978-3-540-30140-0_25">10.1007/978-3-540-30140-0_25</a>
eng
info:eu-repo/semantics/altIdentifier/doi/10.1007/978-3-540-30140-0_25
info:eu-repo/semantics/altIdentifier/issn/0302-9743
info:eu-repo/semantics/altIdentifier/issn/1611-3349
info:eu-repo/semantics/altIdentifier/isbn/9783540230250
info:eu-repo/semantics/altIdentifier/isbn/9783540301400
info:eu-repo/semantics/closedAccess