Résumé:
Le problème de reconnaissance de plans discrets est un problème de géométrie discrète. C'est aussi un problème de géométrie algorithmique posé sur un ensemble de points à coordonnées entières. On peut le résoudre par différentes méthodes générales (programmation linéaire, calculs d'enveloppes convexes, algorithmes de détection de collision) ou par des méthodes spécialement conçues dans le cadre de la géométrie discrète. Nous présenterons dans cette dernière perspective un algorithme de reconnaissance de plan discret, qui semble fonctionner en temps presque linéaire dans la pratique malgré une désastreuse borne de complexité en O(n7 ). Cette borne naive est la plus petite qu'on sache montrer, tandis que les pires exemples connus ne sont même pas en O(n2 ), ce qui laisse une importante marge de progrés d'un coté ou de l'autre pour améliorer notre connaissance de cet algorithme.