Simplification géometrique optimale pour le rendu

Lilan Buzer (A2SI)

Résumé:

Pour une chaîne polygonale donnée et un critère d'approximation fixé, nous résolvons le problème min-# consistant à trouver une sous-chaîne ordonnée ayant un nombre minimal de sommets. Notre méthode calcule une approximation qui respecte la forme de la chaîne originale. De plus, notre algorithme atteint une complexité quasi linéaire. Son implémentation est basée sur des structures de données classiques. A notre connaissance, c'est le seul algorithme à fournir l'ensemble de ces avantages.