The shuffling bufferReport as inadecuate

The shuffling buffer - Download this document for free, or read online. Document in PDF available to download.

1 PRISME - Geometry, Algorithms and Robotics CRISAM - Inria Sophia Antipolis - Méditerranée

Abstract : The complexity of randomized incremental algorithms is analyzed with the assumption 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 with the on-line nature of the algorithm.
We present the shuffling buffer technique to introduce sufficient randomness to guarantee an improvement on the worst case complexity by knowing only k data in advance.
Typically, an algorithm with $On^2$ worst-case complexity and On or On log n randomized complexity has an On^2 log k-k complexity for the shuffling buffer.
We illustrate this with binary search trees, the number of Delaunay triangles or the number of trapezoids in a trapezoidal map created during an incremental construction.

Author: Olivier Devillers - Philippe Guigue -



Related documents