Résumé | Prenons un nombre pair, 2n, de points dans le plan, en position convexe. Le nombre de couplages parfaits de ces 2n points qui ne présentent pas de croisements d'arêtes (si celles-ci sont tracées par des segments), est bien connu : c'est le n-ième nombre de Catalan.
Mais que se passe-t-il si, au lieu d'être en position convexe, les points sont « presque » en position convexe : 2n-1 sont en position convexe, et le dernier se trouve à l'intérieur du polygone ? La réponse dépend alors des positions de tous les points, mais Ruiz-Vargas et Welzl ont démontré une élégante formule d'énumération qui ne fait intervenir que les positions des points par rapport à un petit nombre de droites. Je présenterai la preuve de ce résultat, et essaierai de discuter de la possibilité d'exploiter une telle formule pour faire de la génération aléatoire. |