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)
13 Downloads (Pure)

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 languageUndefined
Pages (from-to)30:1-30:28
Number of pages28
JournalACM transactions on algorithms
Volume8
Issue number3
DOIs
Publication statusPublished - Jul 2012

Keywords

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

Cite this