Extreme Points Under Random Noise

V. Damerow, C. Sohler, in: Proceedings of the 12th European Symposium on Algorithms (ESA’04), Berlin, Heidelberg, 2004.

Download
No fulltext has been uploaded.
Conference Paper | Published | English
Author
;
Abstract
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 &#916;. Our results are parametrized by the variance of the noise distribution. For large variance we essentially consider the average case for distribution &#916; 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 &#963;² and the uniform distribution in a hypercube of side length &epsilon. For these noise distributions we show upper bounds of O( (1/ &#963; )^d * log^3/2 * d - 1 n ) and O( ( (n log n) / &#949; )^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.
Publishing Year
Proceedings Title
Proceedings of the 12th European Symposium on Algorithms (ESA'04)
LibreCat-ID

Cite this

Damerow V, Sohler C. Extreme Points Under Random Noise. In: Proceedings of the 12th European Symposium on Algorithms (ESA’04). Berlin, Heidelberg; 2004. doi:10.1007/978-3-540-30140-0_25
Damerow, V., & Sohler, C. (2004). Extreme Points Under Random Noise. In Proceedings of the 12th European Symposium on Algorithms (ESA’04). Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-30140-0_25
@inproceedings{Damerow_Sohler_2004, place={Berlin, Heidelberg}, title={Extreme Points Under Random Noise}, DOI={10.1007/978-3-540-30140-0_25}, booktitle={Proceedings of the 12th European Symposium on Algorithms (ESA’04)}, author={Damerow, Valentina and Sohler, Christian}, year={2004} }
Damerow, Valentina, and Christian Sohler. “Extreme Points Under Random Noise.” In Proceedings of the 12th European Symposium on Algorithms (ESA’04). Berlin, Heidelberg, 2004. https://doi.org/10.1007/978-3-540-30140-0_25.
V. Damerow and C. Sohler, “Extreme Points Under Random Noise,” in Proceedings of the 12th European Symposium on Algorithms (ESA’04), 2004.
Damerow, Valentina, and Christian Sohler. “Extreme Points Under Random Noise.” Proceedings of the 12th European Symposium on Algorithms (ESA’04), 2004, doi:10.1007/978-3-540-30140-0_25.

Export

Marked Publications

Open Data LibreCat

Search this title in

Google Scholar
ISBN Search