Résolution de contraintes géométriques en guidant une méthode homotopique par la géométrie

Suivant le domaine où on les sollicite, les solutions d'un système de contraintes géométriques peuvent être: - formelles et exactes: elles prennent alors la forme d'un plan de construction, qui est une suite d'instructions primitives (par exemple des constructions à la règle et au compas) produisant toutes les solutions; - numériques et approchées: le système de contraintes est ré-écrit en un système d'équations; on peut chercher une ou toutes ses solutions, réelles ou complexes. Ces deux attentes sont distinctes mais pas incompatibles. La première est souvent atteinte en appliquant de manière systématique des règles dérivées de lemmes de géométrie. Cependant beaucoup de problèmes, la plupart quand on se place dans un contexte 3D, résistent à cette simplification du raisonnement humain. Les traduire en systèmes d'équations grâce à la géométrie analytique permet alors de les résoudre grâce à des méthodes numériques générales pour répondre au second objectif. Elles sont efficaces quand elles ne recherchent qu'une solution. Par contre, de par la nature des problèmes traités, trouver toutes les solutions en une fois conduit à une complexité exponentielle. Les méthodes par continuation, ou homotopie, permettent d'obtenir toutes les solutions d'un système d'équations polynomiales. Très étudiées des points de vue de la géométrie algébrique et de la topologie différentielle depuis au moins 30 ans, elles bénéficient d'une assise théorique permettant de les rendre très fiables. Leur application à des systèmes d'équations issus de problèmes de géométrie reste cependant coûteuse et difficilement sujette aux raisonnements permis par l'origine géométrique du problème, en dehors de ceux réalisés en amont sur le système lui-même, car elles opèrent hors de l'espace des figures géométriques. Notre travail a pour objet la spécialisation d'une méthode par continuation à des systèmes de contraintes géométriques. Leur origine permet de simplifier et de justifier sa mise en œuvre dans l'espace des figures, où des raisonnements géométriques sont possibles. On aborde également les cas où l'ensemble de solutions d'un problème contient des éléments isolés et des continuums. Des solutions proches d'une esquisse fournie par un utilisateur sont d'abord trouvées. La recherche d'autres solutions, malgré sa complexité exponentielle, est rendue envisageable par une approche itérative. Une méthode de décomposition, qui simplifie des problèmes traditionnellement considérés comme indécomposables, est proposée pour maîtriser le coût de la résolution.

R. Imbach

Thèse - Université de Strasbourg - 2013

@Phdthesis{8-Imba13,
 author = {Imbach, R.},
 title = {R\'esolution de contraintes g\'eom\'etriques en guidant une m\'ethode homotopique par la g\'eom\'etrie},
 school = {Universit\'e de Strasbourg},
 month = {Oct},
 year = {2013},
 keywords = {R\'esolution de contraintes g\'eom\'etriques; M\'ethodes par continuation; Homotopie; M\'ethodes Hybrides; Mod\'elisation g\'eom\'etrique},
 x-language = {FR},
 url = {http://publis.icube.unistra.fr/8-Imba13}
}