The shuffling buffer

Olivier Devillers 1 Philippe Guigue 1
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 $O(n^2)$ worst-case complexity and O(n) or O(n log n) randomized complexity has an O((n^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.
Type de document :
Article dans une revue
International Journal of Computational Geometry and Applications, World Scientific Publishing, 2001, 11, pp.555-572. 〈http://www.worldscinet.com/ijcga/11/1105/S021819590100064X.html〉. 〈10.1142/S021819590100064X〉
Liste complète des métadonnées

https://hal.inria.fr/inria-00412567
Contributeur : Olivier Devillers <>
Soumis le : mercredi 2 septembre 2009 - 10:31:46
Dernière modification le : jeudi 11 janvier 2018 - 17:00:01
Document(s) archivé(s) le : mardi 15 juin 2010 - 20:22:47

Fichier

TheShufflingBuffer.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Olivier Devillers, Philippe Guigue. The shuffling buffer. International Journal of Computational Geometry and Applications, World Scientific Publishing, 2001, 11, pp.555-572. 〈http://www.worldscinet.com/ijcga/11/1105/S021819590100064X.html〉. 〈10.1142/S021819590100064X〉. 〈inria-00412567〉

Partager

Métriques

Consultations de la notice

246

Téléchargements de fichiers

84