TY - JOUR

T1 - Smoothed analysis of left-to-right maxima with applications

AU - Damerow, Valentina

AU - Manthey, Bodo

AU - Heide, Friedhelm Meyer Auf Der

AU - Racke, Harald

AU - Scheideler, Christian

AU - Sohler, Christian

AU - Tantau, Till

PY - 2012/7

Y1 - 2012/7

N2 - A left-to-right maximum in a sequence of n numbers s1, sn 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 nnumbers si ε [0, 1] that are perturbed by uniform noise from the interval [-ε, ε], the expected number of left-to-right maxima is Θ (Mathematical Equation Presented) 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 Θ (Mathematical Equation Presented), 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.

AB - A left-to-right maximum in a sequence of n numbers s1, sn 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 nnumbers si ε [0, 1] that are perturbed by uniform noise from the interval [-ε, ε], the expected number of left-to-right maxima is Θ (Mathematical Equation Presented) 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 Θ (Mathematical Equation Presented), 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.

KW - Binary search trees

KW - Convex hull

KW - Motion complexity

KW - Quicksort

KW - Smoothed analysis

UR - http://www.scopus.com/inward/record.url?scp=84864839789&partnerID=8YFLogxK

U2 - 10.1145/2229163.2229174

DO - 10.1145/2229163.2229174

M3 - Article

AN - SCOPUS:84864839789

SN - 1549-6325

VL - 8

JO - ACM Transactions on Algorithms

JF - ACM Transactions on Algorithms

IS - 3

M1 - 30

ER -