Robustesse et dégénérescences

Les algorithmes de géométrie algorithmique ont longtemps eu des difficultés pour passer de la théorie à la pratique. La raison principale est que les algorithmes sont conçus dans le cadre de la géométrie euclidienne réelle, c'est à dire que l'on suppose que l'on peut utiliser les théorèmes géométriques et mathématiques dans nos algorithmes. C'est malheureusement faux, car la machine ne sait pas correctement représenter des réels et n'effectue en général que des calculs arrondis.

Combinatoire et prédicats

La plupart des algorithmes peuvent être vu sous un angle combinatoire. L'information calculée est de nature discrète, par exemple, étant donné un ensemble de points on cherche un ordre sur ces points (tri) un sous-ensemble de ces points (enveloppe convexe) ou des triplets formés par ces points (triangulation de Delaunay).

Pour prendre ces décisions, l'algorithme combinatoire va se poser des questions géométriques élémentaires que l'on appelle prédicats, par exemple, comparaison de l'abscisse de deux points, orientation d'un triangle défini par trois points ou appartenance d'un point au cercle passant par trois autres points.


Cohérence géométrique

C'est une incohérence entre les réponses à différents prédicats qui provoque des problèmes.

Exemple: tourner autour de v

t=t0
do
  let vpq vertices of t ccw
  t = neighbor of t through qv
while t not equal to t0

Le petit programme ci dessus permet de parcourir tous les triangles incident à v dans une triangulation. Le calcul du triangle suivant dans cet ordre repose sur un test d'orientation du triangle, une erreur dans ce test fera boucler le programme (voir figure ci contre).

On débute au triangle t0=vr1r2=vpq
on passe au voisin vr2r3=vpq
puis au voisin vr4r3=vpq avec un erreur d'orientation
et on boucle entre vr2r3 et vr4r3

Ce résultat est incohérent puisque d'après les tests d'orientations r2 et r4 sont du même coté de l'arête vr3 ce qui est incompatible avec l'existence des triangles vr2r3 et vr4r3 dans la triangulation.


Solutions

Les incohérences peuvent provenir d'erreurs d'arrondis dans l'évaluation des prédicats. L'utilisation d'arithmétiques exactes ainsi que d'autres outils permet d'obtenir des prédicats exacts, et donc cohérents, ayant une efficacité raisonnable.

Les prédicats ont généralement trois réponses, deux réponses principales (dedans, dehors) et une réponse «limite» entre ces deux cas (sur le bord). On dit que la configuration est dégénérée. De nombreux algorithmes ne prévoient pas les configurations dégénérées, on utilise alors des techniques de simulation de non dégénérescences: les prédicats ne répondent jamais que l'on est dans la cas limite, on choisit toujours une des deux autres situations, mais il faut que ces choix soit cohérents entre eux.


Last modified: Tue Apr 11 10:07:56 MET DST 2000 Olivier Devillers Thèmes Accueil PRISME same page in english