Convexe signifie qu'aucun des points n'est "au milieu" des autres : je ne peux pas entourer un point avec des segments entre les autres points

Par exemple, cet autre polygone n'est pas convexe

Et comme on aime découper en triangle, il y a des gens qui étudient toutes les façons de découper en triangle (genre moi je fais ça parfois).

Car oui, il y a plusieurs façons de faire ce découpage. Pour l'octogone de tout à l'heure, je vous ai montré un exemple mais il y a 132 façons différentes. On sait compter ça en combinatoire, ça s'appelle les nombres de Catalan, c'est mes nombres préférés

https://fr.wikipedia.org/wiki/Nombre_de_Catalan

Et ce qui va nous intéresser aujourd'hui, c'est qu'on peut passer d'une triangulation à l'autre en modifiant juste une diagonale. Ça s'appelle un "flip" on choisit une diagonale, on la supprime et on la remplace par la seule autre diagonale possible qui forme une triangulation

Voilà un exemple

Et ce qu'on peut démontrer assez facilement, c'est que sur un polygone : on peut passer de n'importe quelle triangulation à n'importe quelle autre juste en faisant une série de "flip".

Voyez par exemple sur cette page le "graphe de flip" des 14 triangulations d'un hexagone

https://www.researchgate.net/figure/The-flip-graph-of-a-convex-hexagon-the-graph-of-the-3-dimensional-associahedron_fig4_365369610

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

On peut se demander pourquoi on veut savoir ça. Donc déjà je vous ai dit que les triangles et les triangulations, on aimait bien ça mais peut-être ça vous convainc pas assez. Mais il se trouve qu'en plus, les triangulations peuvent être transformées en plein d'autres choses !!

Par exemple, si je mets un point dans chaque triangle et que je relis ensemble les points qui sont dans des triangles qui se touchent, j'obtiens une autre structure qu'on appelle un arbre binaire

Et les arbres binaires, c'est un truc très très courant en informatique, en particulier en algorithmique parce que ça permet de représenter tout un tas de donnés en les séparant à chaque fois en 2 groupes.

Par exemple je vais mettre tous les mots qui commencent pat une lettre entre A et M à gauche, et tous les mots qui commencent par N... Z à droite. Puis je vais redécouper à gauche et à droite en 2 nouveaux groupes etc.

Donc l'arbre binaire modélise plein de trucs intéressant et se retrouve dans plein d'algo. Et en plus, le "flip" sur la triangulation correspond à ce qu'on appelle la "rotation" sur l'arbre binaire qui permet de faire pencher l'arbre sur la gauche ou sur la droite.

C'est une opération très courante et utile. Ce qui fait qu'on aimerait bien savoir comment on calcule la "distance de rotation" entre deux arbres, aka la "distance de flip" entre les triangulations et surtout savoir si on peut le faire de façon efficace

Donc là, on va parler un "tout petit peu" de théorie de la complexité. Un truc qui prend la tête de toute la communauté informatique c'est le problème "P = NP"

https://fr.wikipedia.org/wiki/Probl%C3%A8me_P_%E2%89%9F_NP

En gros, en théorie de la complexité, on range les problèmes en fonction de à quel point on peut les résoudre de façon efficace ou non. Et en gros, on a des problèmes qu'on sait résoudre pas trop mal et d'autres pas du tout

Ceux qu'on sait pas résoudre, on a jamais réussi à démonter que c'était vraiment pas possible de le faire de façon efficace, mais on pense que c'est une impossibilité structurelle inhérente au problème lui même, c'est la conjoncture que "P est différent de NP"

Mais on a mis tous les problèmes irrésolubles ensemble et on a démontré qu'ils étaient équivalent entre eux (en gros, si on sait en résoudre un, on sait résoudre les autres _ si je sais calculer un certain bidule dans un graphe, je vais réussir à calculer une solution d'une certaine équation)

Et Joseph Dorfer a démontré que le calcul de la distance de flip est NP-complet donc en gros, il est équivalent à tous les autres problèmes relous qu'on a déjà. Ça veut dire que c'est PAS LA PEINE d'essayer de se prendre la tête à trouver un algorithme efficace parce qu'on VA PAS Y ARRIVER

Mais c'est pas grave hein ! Ça veut dire qu'on peut mettre son énergie ailleurs, par exemple calculer des solutions approchées

Donc voilà, je vous ai résumé le résultat. Je ne sais pas du tout comment il le démontre car je n'ai pas encore lu l'article. Assez récemment, un autre article démontrait la NP-complétude de la distance de flip pour les polygones non convexe

https://arxiv.org/abs/1209.0579

L'un des auteurs est le directeur de thèse de Joseph Dorfer avec qui j'ai beaucoup discuté de ce problème. Une triangulation d'un polygone non convexe ça peut ressembler à ça

La preuve fabriquait des espèces de "tunnels" comme sur l'image donc, une chose est sûre, la nouvelle démonstration de Joseph Dorfer doit être très différente. En tout cas, c'est un magnifique résultat et je vais devoir mettre à jour tous mes projets de recherche !!

Je rajoute en conclusion : ce résultat signifie que si vous trouvez un algorithme efficace pour calculer la distance de flip entre 2 triangulations, alors vous cassez la sécurité informatique mondiale 🤷🏼‍♀️

(pourquoi ? Parce que les 2 sont des algorithmes "NP-complet" donc équivalent)

@pyviv

Est ce qu'il est prouvé que tout les problèmes NP-complet ont la même complexité ?

N'est il pas possible d'envisager qu'il y ait des classes de complexité différentes, dans le même genre qu'il y a des infinis plus grands que d'autres ?