En géométrie algorithmique, de nombreux algorithmes nécessitent de répondre de façon répétée à un même prédicat: étant donné un point du plan, est-il à gauche d’une droite donnée? à l’intérieur d’un cercle donné? Combien de droites coupent quatre droites données de l’espace? À travers ce dernier problème, nous présentons une méthode systématique d’évaluation polynomiale de prédicats géométriques fondée sur la théorie des invariants d’une action de groupe.
This document was translated from LATEX by HEVEA.