Smoothed analysis of left-to-right maxima with applications

Valentina Damerow, Bodo Manthey, Friedhelm Meyer auf der Heide, Heide Harald Räcke, Christian Scheideler, Christian Sohler, Till Tantau

Research output: Contribution to journalArticleAcademicpeer-review

5 Citations (Scopus)

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 paper 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$ in $[0,1]$ that are perturbed by uniform noise from the interval $[-\epsilon,\epsilon]$, the expected number of left-to-right maxima is $\Theta(\sqrt{n/\epsilon} + \log n)$ for $\epsilon > 1/n.$ For Gaussian noise with standard deviation $\sigma$ we obtain a bound of $O((\log^{3/2} n)/ \sigma + \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 $\Theta(\sqrt{n/\epsilon} + \log n)$ and $\Theta(\frac{n}{\epsilon+1} \sqrt{n/\epsilon} + n \log n)$, respectively, for uniform random noise from the interval $[-\epsilon,\epsilon]$. 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 paper. 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.
Original language Undefined 30:1-30:28 28 ACM transactions on algorithms 8 3 https://doi.org/10.1145/2229163.2229174 Published - Jul 2012

Keywords

• Smoothed Analysis
• EWI-20667
• Convex hull
• Binary search trees
• Quicksort
• METIS-289628
• IR-80970
• Left-to-right maxima