Smoothed analysis of left-to-right maxima with applications

DOI10.1145/2229163.2229174zbMath1295.68233OpenAlexW2029151602MaRDI QIDQ3189072

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

Publication date: 9 September 2014

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2229163.2229174

zbMATH Keywords

convex hullbinary search treesquicksortsmoothed analysismotion complexity

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Searching and sorting (68P10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Data structures (68P05)

Related Items (4)

The multiplicity of left-to-right maxima in geometrically distributed words ⋮ Smoothed Analysis of Local Search Algorithms ⋮ On smoothed analysis of quicksort and Hoare's find ⋮ Smoothed analysis of partitioning algorithms for Euclidean functionals

This page was built for publication: Smoothed analysis of left-to-right maxima with applications