Presentation
Smoothed number of extreme points under uniform noise
Author/s | Damerow, Valentina
Sohler, Christian |
Publication Date | 2004 |
Deposit Date | 2017-03-02 |
Published in |
|
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 ... 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. |
Project ID. | 872-8/2
IST-1999-14186 |
Citation | Damerow, V. y Sohler, C. (2004). Smoothed number of extreme points under uniform noise. En 20th European Workshop on Computational Geometry, Sevilla. |
Files | Size | Format | View | Description |
---|---|---|---|---|
Smoothed number of extreme points ... | 200.0Kb | [PDF] | View/ | |