Résumé : Le problème est de construire des arbres binaires éloignés vis-à-vis de la distance de rotation, ce qui équivaut à construire des expressions parenthésées éloignées vis-à-vis de l'associativité, ou encore des triangulations de polygone éloignées vis-a-vis de l'échange de diagonales. On présentera la magnifique solution de Sleator-Tarjan-Thurston basée sur la géométrie hyperbolique, qui est optimale mais valable seulement pour une taille assez grande (non effective), ainsi qu'une méthode combinatoire basée sur une notion de séparatrice dans les associaèdres, qui est (pour le moment) non optimale, mais valable pour toute taille.
| Dernière modification : Monday 18 March 2024 |
|
Contact pour cette page : Cyril.Banderier at lipn.univ-paris13.fr |