Elektrine lite

← Feed

@pyviv@social.sciences.re

2026-03-20 11:59 UTC

Maintenant qu'on sait ça, on se pose une question toute simple : voilà 2 triangulations de mon polygone, c'est quoi la façon la plus rapide de passer de l'une à l'autre en faisant des flips? (c'est à dire le moins de flip possible)

Replies (1)

  • @pyviv@social.sciences.re 2026-03-20 12:11

    Et là, C'EST LE DRAME !! On ne sait pas !! Évidemment, on peut calculer le graphe complet de toutes les triangulations, mais heu il y en a beaucoup, plus précisément le nombre de triangulations augmente de façon exponentielle par rapport au nombre de sommets. Pour un polygone de 50 sommets, j'ai déjà plusieurs milliards de milliards de milliards de triangulations possibles. Donc no way de calculer le graphe complet 🤷🏼‍♀️

    Open ##2339760