---
res:
bibo_abstract:
- 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 Θ(&sqrt;n/ε + log n) for ε>1/n. For Gaussian noise with standard deviation
σ we obtain a bound of O((log3/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 Θ(&sqrt;n/ε + log n) and Θ(n/ε+1&sqrt;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.@eng
bibo_authorlist:
- foaf_Person:
foaf_givenName: Valentina
foaf_name: Damerow, Valentina
foaf_surname: Damerow
- foaf_Person:
foaf_givenName: Bodo
foaf_name: Manthey, Bodo
foaf_surname: Manthey
- foaf_Person:
foaf_givenName: Friedhelm
foaf_name: Meyer auf der Heide, Friedhelm
foaf_surname: Meyer auf der Heide
foaf_workInfoHomepage: http://www.librecat.org/personId=15523
- foaf_Person:
foaf_givenName: Harald
foaf_name: Räcke, Harald
foaf_surname: Räcke
- foaf_Person:
foaf_givenName: Christian
foaf_name: Scheideler, Christian
foaf_surname: Scheideler
foaf_workInfoHomepage: http://www.librecat.org/personId=20792
- foaf_Person:
foaf_givenName: Christian
foaf_name: Sohler, Christian
foaf_surname: Sohler
- foaf_Person:
foaf_givenName: Till
foaf_name: Tantau, Till
foaf_surname: Tantau
bibo_doi: 10.1145/2229163.2229174
bibo_issue: '3'
dct_date: 2012^xs_gYear
dct_publisher: ACM@
dct_title: Smoothed analysis of left-to-right maxima with applications@
...