The shuffling buffer

Olivier Devillers 1 Philippe Guigue 1
1 GEOMETRICA - Geometric computing
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 O(n2) worst-case complexity and O(n) or O(nlog n) randomized complexity has an O(n2 (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.
Document type :
Conference papers
Complete list of metadatas

https://hal.inria.fr/hal-01179052
Contributor : Olivier Devillers <>
Submitted on : Tuesday, July 21, 2015 - 3:20:26 PM
Last modification on : Saturday, January 27, 2018 - 1:30:54 AM

Identifiers

  • HAL Id : hal-01179052, version 1

Collections

Citation

Olivier Devillers, Philippe Guigue. The shuffling buffer. 13th Canadian Conference on Computational Geometry, 2001, Waterloo, Canada. ⟨hal-01179052⟩

Share

Metrics

Record views

113