Elektrine lite

← Feed

@pyviv@social.sciences.re

2026-03-20 12:11 UTC

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 🤷🏼‍♀️

Replies (1)

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

    Donc la question qui était ouverte jusqu'à présent, c'est étant donné 2 triangulations d'un polygone, quelle est la complexité du calcul de la "distance de flip", c'est à dire le plus court chemin entre les deux. "complexité" en gros ça veut dire le temps théorique en fonction du nombre de sommets dans mon polygone

    Open ##2339761