The shuffling buffer

The complexity of randomized incremental algorithms is analyzed with the as sumption of a random order of the input. To guarantee this hypothesis, the n data have to be known in advance in order to be mixed what contradicts wi th the on-line nature of the algorithm. We present the shuffling buffer tec hnique to introduce sufficient randomness to guarantee an improvement on th e worst case complexity by knowing only k data in advance. Typically, an al gorithm with O(n(2)) worst-case complexity and O(n) or O(n log n) randomize d complexity has an O(n(2)logk/k) complexity for the shuffling buffer. We i llustrate this with binary search trees, the number of Delaunay triangles o r the number of trapezoids in a trapezoidal map created during an increment al construction.