Sie befinden Sich nicht im Netzwerk der Universität Paderborn. Der Zugriff auf elektronische Ressourcen ist gegebenenfalls nur via VPN oder Shibboleth (DFN-AAI) möglich. mehr Informationen...
Smoothed analysis of left-to-right maxima with applications
Ist Teil von
ACM transactions on algorithms, 2012-07, Vol.8 (3), p.1-28
Erscheinungsjahr
2012
Quelle
Alma/SFX Local Collection
Beschreibungen/Notizen
A left-to-right maximum in a sequence of
n
numbers
s
1
, …,
s
n
is a number that is strictly larger than all preceding numbers. In this article we present a smoothed analysis of the number of left-to-right maxima in the presence of additive random noise. We show that for every sequence of
n
numbers
s
i
∈ [0,1] that are perturbed by uniform noise from the interval [-ϵ,ϵ], the expected number of left-to-right maxima is Θ(√
n
/ϵ + log
n
) for ϵ>1/
n
. For Gaussian noise with standard deviation σ we obtain a bound of
O
((log
3/2
n
)/σ + log
n
).
We apply our results to the analysis of the smoothed height of binary search trees and the smoothed number of comparisons in the quicksort algorithm and prove bounds of Θ(√
n
/ϵ + log
n
) and Θ(
n
/ϵ+1√
n
/ϵ +
n
log
n
), respectively, for uniform random noise from the interval [-ϵ,ϵ]. Our results can also be applied to bound the smoothed number of points on a convex hull of points in the two-dimensional plane and to
smoothed motion complexity,
a concept we describe in this article. We bound how often one needs to update a data structure storing the smallest axis-aligned box enclosing a set of points moving in
d
-dimensional space.