L'objectif de cet article est de compter les courbes possédant \( n \) auto-intersections et de décrire comment j'envisage la programmation (en force brute) d'un tel décompte.
Il semble obligatoire de préciser deux ou trois petites choses, sinon la réponse est trivialement qu'il y a un nombre infini de telles courbes quel que soit \( n \).
Les critères d'éligibilité d'une courbe pour ce problème sont :
Ce qu'on cherche à comptabiliser à vrai dire, ce sont les classes d'équivalence de ces courbes : si on peut passer d'une courbe à l'autre au moyen d'une déformation (homéomorphisme), alors on considère que c'est la même courbe.
L'orientation a son importance : si une courbe (modulo déformation) n'est pas superposable à son image miroir, alors on tient deux courbes et non une seule (on parle de chiralité, du grec χείρ = main).
|
|
|
|
|
|
Intuitivement, il n'existe qu'une seule courbe sans intersection ; on peut prendre par exemple une demi-droite pour se la représenter.
Combien de courbes avec 1 intersection ? On voit la boucle qui tourne à gauche et la boucle qui tourne à droite, et rien d'autre.
Peut-on continuer ? Si on prolonge l'une des deux boucles précédentes, on obtient ... ?
L'idée centrale est que pour obtenir une courbe avec \( n + 1 \) intersections, il faut partir d'une courbe avec \( n \) intersections et créer une intersection supplémentaire en traversant une arète appartenant à la face (zone) dans laquelle se situe l'extrémité de la courbe.
Qu'est-ce qui garantit qu'il n'existe pas plusieurs façons d'obtenir la même courbe ? A mon sens, c'est la réversibilité des opérations : étant donné une courbe avec \( n \) intersections, on est capable de remonter le temps, dire quelle était la dernière arête traversée, la "dé-traverser", et recommencer jusqu'à revenir à la courbe initiale sans intersection. S'il existait plusieurs façons d'obtenir la même courbe, il ne pourrait y avoir une telle réversibilité.
Obtient-on toutes les courbes ainsi ? Oui, je ne vois pas comment il pourrait en être autrement... Etant donné une courbe à \( n \) intersections et sa fonction \( f \), il doit bien y avoir une subdivision de \( ]-\infty, 0 ] \), \( (t_1 < t_2 < \dots < t_n < 0 ) \) telle que les points d'intersection sont les \( f(t_i) \). Si on tronque l'intervalle de définition de f à \( ] -\infty, \frac{t_{n-1} + t_{n}}{2} ] \), et qu'on retranslate de \( \frac{t_{n-1} + t_{n}}{2} \), alors la fonction \( g(t) = f \left ( t - \frac{t_{n-1} + t_{n}}{2} \right ) \) ainsi obtenue correspond bien à une courbe avec \( n - 1 \) intersections qui satisfait à nos critères ... et qui donc par hypothèse de récurrence fait partie de la liste déjà établie... On n'a fait que prolonger cette courbe.
Conclusion, avec un arbre d'exploration de tous les choix possibles, sur une profondeur \( n \), on peut énumérer toutes les courbes avec \( n \) intersections.
Nous considérerons l'exemple de la courbe à 2 intersections obtenue en faisant une boucle à gauche, puis en réinjectant l'extrémité dans la petite zone ainsi obtenue.
On peut numéroter les points d'intersection, comme suit :
Par convention, 0 est le point à l'infini. Notre dessin n'ayant pas une taille infinie, nous sommes bien obligés de représenter \( 0 \) à distance finie du reste !
Par convention, \( n + 1 \) est l'extrémité finie de la courbe (quand la courbe comporte \( n \) intersections)
Les autres points (de \( 1 \) à \( n \)) sont numérotés selon le rang de leur création par auto-intersection, à paramètre \( t \) croissant.
La finitude du dessin pose problème : quand on est à l'extérieur, il ne faudrait pas pouvoir contourner le point \( 0 \) ; cela n'aurait pas de sens. Pour matérialiser cette impossibilité, nous allons créer une arête fictive "à l'infini", un "mur" infranchissable, reliant 0 à 0, et qui encadre le dessin.
Il sera utile de pouvoir distinguer plusieurs variantes de chaque point d'intersection...
Noter que \( 0 \) possède \( 2 \) variantes ; le dernier point (\( n + 1 \)) n'en possède qu'une ; tous les autres en possèdent \( 4 \).
On peut presque voir chaque variante de point comme un couple (ce point, la zone depuis laquelle on le regarde).
"Presque", parce qu'en fait (comme l'illustre parfaitement l'image ci-dessus avec le point 1) cela peut arriver qu'une zone puisse regarder un même point de 2 façons différentes, si une arête à traverser liée à ce point mène de la zone à elle-même !
Une meilleure définition serait que ce sont des "coins de zones".
La courbe de l'exemple délimite 3 zones,
Chacune de ces zones est délimitée par un cycle d'arêtes orientées, cycle que par convention nous orienterons dans le sens contraire des aiguilles d'une montre.
Chaque arête (non orientée) de la courbe doit être vue comme étant dédoublée, une arête orientée dans un sens ainsi qu'une arête orientée dans l'autre sens.
L'arête orientée que l'on voit dépend de la zone dans laquelle on se trouve, voire (pour l'arête terminale reliant le point \( n \) au point \( n + 1 \)) de quel côté on envisage de la traverser.
Quand on réunit tous les ingrédients ci-dessus, on obtient une représentation informatique de nos courbes. Pour la courbe exemple, cette représentation informatique est la suivante :
On a créé une sorte de graphe, sauf qu'il existe 2 sortes de noeuds :
Chaque sommet pointe vers l'arête qui le suit (dans le sens contraire des aiguilles d'une montre).
Chaque arête pointe vers le sommet qui le suit (dans le sens contraire des aiguilles d'une montre).
Chaque sommet fait partie d'un groupe (représenté sous la forme d'un carré en pointillés) de 1, 2 ou 4 sommets qui portent la même étiquette (typiquement : le numéro d'intersection de la courbe).
Chaque arête A, sauf une (le mur à l'infini), est connectée à une arête partenaire B : B est l'arête qui donne accès à la zone dans laquelle atterrira l'extrémité de la courbe si cette extrémité traverse A. Cette connection est bidirectionnelle. Nous l'avons également représentée sous forme de pointillés entre arêtes.
La couleur des sommets et des arêtes matérialise les zones (même légende que l'image qui précède).
Un sommet particulier représente l'extrémité finie de la courbe, il a été marqué d'un astérisque.
Voici les grandes lignes, selon moi, de l'algorithme force brute pour déterminer le nombre de courbes possédant n intersections :
L'extrémité S de la courbe passe au travers de l'arête orientée Q et se retrouve, ce faisant, téléportée via l'arête orientée partenaire R de Q, de l'autre côté de la même zone (bleue sur le schéma). Le nouvel état s'obtient de façon déterministe à partir de l'ancien par la création/mise à jour/suppression d'un certain nombre de sommets et d'arêtes :
A noter qu'une nouvelle zone est créée (représentée en rouge sur le schéma), c'est l'intérieur de la boucle qui vient d'être créée. A noter que cette zone rouge n'a qu'un sommet et qu'une arête.
En tout point similaire au cas "boucler à gauche". Je ne détaille pas.
L'extrémité E de la courbe passe au travers de l'arête orientée W1 et se retrouve, ce faisant, téléportée via l'arête orientée partenaire W2 de W1, de l'autre côté, dans une zone qui (dans le cas général) n'est pas la même zone, d'où l'utilisation de 2 couleurs sur le schéma, jaune pour la zone de départ et bleu pour la zone d'arrivée.
La zone quittée se retrouve a priori coupée en deux zones par l'opération, d'où l'utilisation de 2 nouvelles couleurs (rouge et vert).
Le nouvel état s'obtient de façon déterministe à partir de l'ancien par la création/mise à jour/suppression d'un certain nombre de sommets et d'arêtes :
Ecueil programmatique à éviter : attention, les noeuds A2 et B2 peuvent tout à fait être le même noeud (cf. la dernière remarque du §10, preuve qu'une zone peut n'avoir qu'un seul sommet).
Cf. mes programmes sur GitHub (A373325).
J'ai commencé par un prototype en C ne permettant que la marche avant (et qu'il a fallu compléter en shell) ; et ai poursuivi en Prolog pour bénéficier du retour-arrière.
La suite obtenue (OEIS A373325) commence comme suit :
\[ 1, 2, 10, 66, 498, 4072, 35144, 315352, 2914074, 27553880, 265387528, ... \]Toute courbe à n intersections peut se voir assigner une chaîne de caractères de la forme :
\[ e_1 \cdot e_2 \cdot (\cdots) \cdot e_n \]où chaque \( e_i \) est un numéro de "choix d'arête à traverser" allant de 1 à < nombre d'arêtes traversables dans l'état dans lequel on est à ce moment là >.
Pour ce faire, il faut adopter une convention, voici celle que je propose :
Exemples :
Il faudrait réussir à tracer effectivement toutes ces courbes, ou en tout cas réussir à tracer une représentante suffisamment jolie de chacune de ces classes d'équivalence de courbes.
Il faudrait concevoir les structures de données (équations, lignes polygonales, courbes de Bézier, ...) de tracé des courbes, et voir comment les transitions entre états opèrent sur ces données supplémentaires...
LR, le 07/06/2024.