Matrix-based implicit representations of algebraic curves and surfaces and applications
Institution:
NiceDisciplines:
Directors:
Abstract EN:
In this thesis, we introduce and study a new implicit representation of rational curves of arbitrary dimensions and propose an implicit representation of rational hypersurfaces. The, we illustrate the advantages of this matrix representation by addressing several important problems of Computer Aided Geometric Design (CAGD) : the curve/curve, curve/surface and surface/surface intersection problems, the point-on-curve and inversion problems, the computation of singularities of rational curves. We also develop some symbolic/numeric algorithms to manipulate these new representations for example : the algorithm for extracting the regular part of a non square pencil of univariate polynomial matrices and bivariate polynomial matrices. In the appendix of this thesis work we present an implementation of these methods in the computeur algebra systems Mathemagix and Maple. In th last chapter, we describe an algorithm which, given a set of univariate polynomials ∱₁,…∱s returns a set of polynomials U₁,…, Us with prescribed degree-bounds such that the degree of gcd (∱₁ + U₁,…, ∱s + Us) is bounded below by a given degree assuming some genericity hypothesis.
Abstract FR:
Dans cette thèse, nous introduisons et étudions une nouvelle représentation implicite des hypersurfaces rationnelles plongées dans un espace projectif de dimension arbitraire. Nous illustrons les avantages de cette représentation matricielle en abordant plusieurs problèmes importants intervenant en conception géométrique assistée par ordinateur : les problèmes d’intersection entre deux courbes, entre une courbe et une surface ou bien encore entre deux surfaces, le problème d’appartenance d’une point à une courbe ou une surface, le problème du calcul de la pré-image d’un point donné par une paramétrisation et enfin le problème du calcul des singularités d’une courbe rationnelle. L’approche développée dans ce travail de thèse est basée sur la combinaison de méthodes symboliques et numériques. En effet, une première étape symbolique consiste à transformer le problème considéré en un réseau de matrices. La deuxième étape consiste alors à calculer les valeurs propres généralisées de ce pinceau à l’aide de méthodes numériques. Pour cela, un algorithme d’extraction de la partie régulière d’un pinceau univarié, respectivement bivarié, de matrices non carrées est présenté. Une implémentation de ces travaux dans les systèmes de calcul formel Mathemagix et Maple est présentée en appendice. Le dernier chapitre est consacré » à un algorithme qui, étant donné un ensemble de polynômes univariés ∱₁,…∱s construit un ensemble de polynômes U₁,…, Us dont les degrés sont prescrits, tels que le degré du pgcd (∱₁ + U₁,…, ∱s + Us) est supérieur ou égal à un entier donné sous des hypothèses de généricité.