HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Reports

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 metadata

https://hal.inria.fr/inria-00072658
Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Wednesday, May 24, 2006 - 10:30:58 AM
Last modification on : Friday, February 4, 2022 - 3:18:55 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

97

Files downloads

122