Le tampon mélangeur

Olivier Devillers 1 Philippe Guigue 1
1 PRISME - Geometry, Algorithms and Robotics
CRISAM - Inria Sophia Antipolis - Méditerranée
Résumé : Les méthodes de randomisation ont eu un grand succès en géométrie algorithmique car elles conduisent fréquemment à des algorithmes plus simples à programmer et parfois plus efficaces que leurs équivalents déterministes. Un algorithme est randomisé lorsque celui-ci effectue des choix aléatoires pour parvenir à ses fins, pour la catégorie des algorithmes incrémentaux à laquelle nous nous intéressons, le hasard intervient, par exemple, dans l'ordre d'insertion des données. L'analyse de tels algorithmes est alors faite en moyenne sur les différents ordres possibles. Cependant, choisir un ordre d'insertion aléatoire nécessite d'attendre l'ensemble des données avant de les insérer, ce qui fait que l'algorithme n'est plus en ligne. Une solution possible consiste, cependant, à intercaler un tampon mélangeur de taille $k$ entre le processus qui fournit les données et l'entrée de l'algorithme afin d'effectuer un mélange local de l'ordre initial nous permettant ainsi d'introduire assez de randomisation pour nous garantir une amélioration de la complexité moyenne d'algorithmes en ligne dépendant de l'ordre d'insertion. Ainsi après avoir illustré ce type de technique sur le problème du tri, nous donnons quelques résultats obtenus pour des problèmes plus géométriques tels que la triangulation de Delaunay ou le cloisonnement vertical de segments pour lesquels il existe des algorithmes incrémentaux. Typiquement, pour un algorithme randomisé en $O(n \log n)$ ou $O(n)$, le cas le pire est au moins quadratique et l'utilisation des stratégies proposées permet d'obtenir une complexité $O(\fracn^2 \log k{k})$.}
Type de document :
Rapport
[Rapport de recherche] RR-3988, INRIA. 2000, pp.38
Liste complète des métadonnées

https://hal.inria.fr/inria-00072658
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 10:30:58
Dernière modification le : samedi 27 janvier 2018 - 01:31:03
Document(s) archivé(s) le : dimanche 4 avril 2010 - 23:17:18

Fichiers

Identifiants

  • HAL Id : inria-00072658, version 1

Collections

Citation

Olivier Devillers, Philippe Guigue. Le tampon mélangeur. [Rapport de recherche] RR-3988, INRIA. 2000, pp.38. 〈inria-00072658〉

Partager

Métriques

Consultations de la notice

224

Téléchargements de fichiers

197