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})$.}
Document type :
Reports
Complete list of metadatas

https://hal.inria.fr/inria-00072658
Contributor : Rapport de Recherche Inria <>
Submitted on : Wednesday, May 24, 2006 - 10:30:58 AM
Last modification on : Saturday, January 27, 2018 - 1:31:03 AM
Long-term archiving on : Sunday, April 4, 2010 - 11:17:18 PM

Identifiers

  • 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⟩

Share

Metrics

Record views

236

Files downloads

225