0000000000096610
AUTHOR
Dominique Michelucci
On the reducibility of geometric constraint graphs
Geometric modeling by constraints, whose applications are of interest to communities from various fields such as mechanical engineering, computer aided design, symbolic computation or molecular chemistry, is now integrated into standard modeling tools. In this discipline, a geometric form is specified by the relations that the components of this form must verify instead of explicitly specifying these components. The purpose of the resolution is to deduce the form satisfying all these constraints. Various methods have been proposed to solve this problem. We will focus on the so-called graph-based or graph-based methods with application to the two-dimensional space.
Sur la réductibilité des graphes de contraintes géométriques
La modélisation géométrique par contraintes dont les applications intéressent des communautés issues de divers domaines tels l'ingénierie mécanique, la conception assistée par ordinateur, le calcul symbolique ou la chimie moléculaire est maintenant intégré dans les outils standards de modélisation. Dans cette discipline une forme géométrique est spécifiée par les relations que doivent vérifier les composants de cette forme au lieu de spécifier explicitement ces composants. Le but de la résolution est de déduire la forme répondant à toutes ces contraintes. Diverses méthodes ont été proposées pour résoudre ce problème. Nous nous intéresserons spécifiquement aux méthodes dites graphiques ou ba…
REDUCTION OF CONSTRAINT SYSTEMS
Geometric modeling by constraints leads to large systems of algebraic equations. This paper studies bipartite graphs underlaid by systems of equations. It shows how these graphs make possible to polynomially decompose these systems into well constrained, over-, and underconstrained subsystems. This paper also gives an efficient method to decompose well constrained systems into irreducible ones. These decompositions greatly speed up the resolution in case of reducible systems. They also allow debugging systems of constraints.
in Informatique graphique, modélisation géométrique et animation
International audience; no abstract
Reliable Outer Bounds for the Dual Simplex Algorithm with Interval Right-hand Side
International audience; In this article, we describe the reliable computation of outer bounds for linear programming problems occuring in linear relaxations derived from the Bernstein polynomials. The computation uses interval arithmetic for the Gauss-Jordan pivot steps on a simplex tableau. The resulting errors are stored as interval right hand sides. Additionally, we show how to generate a start basis for the linear programs of this type. We give details of the implementation using OpenMP and comment on numerical experiments.
Modélisation géométrique par contraintes
Les modeleurs géométriques classiques permettent de décrire des formes géométriques très variées, mais ils ne prennent pas en compte les intentions de l'utilisateur, et n'utilisent pas son langage, ses gestes, ou son expérience du métier. Cela lui impose notamment d'acquérir un nouveau savoir-faire propre au logiciel, et ralentit la définition des maquettes numériques. Les modeleurs déclaratifs (ou la modélisation par formes caractéristiques (features) en CFAO) entendent combler ce manque. Ce chapitre introduit les formalismes et méthodes de traitement de la modélisation géométrique déclarative à base de contraintes.