Near-optimal parameterization of the intersection of two quadric surfaces : theory, algorithmes and implementation
Paramétrage quasi-optimal de l'intersection de deux quadriques : théorie, algorithmes et implantation
Résumé
This thesis presents a robust and efficient algorithm for the
computation of an exact parameterized form of the intersection curve
of two quadric surfaces defined by implicit equations with rational
coefficients.
For the first time, the parameterization that we obtain contains all
the topological informations of the curve and is simple enough to be
exploited in non-trivial geometric applications.
Many new improvements, in different domains, were necessary to
reach this result. We did a complete study of all possible cases of
intersection, first in $\Pp^3(\C)$ based on the work of Segre, then in
$\Pp^3(\R)$ by exploiting the results of Uhlig on the simultaneous
reduction of two real quadratic forms. This systematic study allowed
us to have a fine understanding the geometry of the intersection of two quadric
surfaces. We are now able to determine all characteristics of the
intersection curve, that is its genus, its singular points, its
algebraic components and connected components, and all the links
between these components. When one exists, we find a rational
parameterization of the components of the curve. In this sense, our
algorithm is optimal. We also made some significant improvements on
the complexity of the radical expression of the coefficients of the
obtained parameterization. Our algorithm is near-optimal in the sense
that the coefficients of the parameterization contain at most one
unnecessary square root in their expression. Our algorithm is optimal in the
worst case, in the sense that for every type of intersection curve
(for example a regular quartic, or a cubic and line, or two conics),
there exist pairs of quadrics for which the number of square
roots in the expression of the coefficients is minimal.
Finally, we made a complete implementation of our algorithm in MuPAD
which allowed us to get previously unheard of performances, in
terms of running time and in terms of the simplicity of the
result.
computation of an exact parameterized form of the intersection curve
of two quadric surfaces defined by implicit equations with rational
coefficients.
For the first time, the parameterization that we obtain contains all
the topological informations of the curve and is simple enough to be
exploited in non-trivial geometric applications.
Many new improvements, in different domains, were necessary to
reach this result. We did a complete study of all possible cases of
intersection, first in $\Pp^3(\C)$ based on the work of Segre, then in
$\Pp^3(\R)$ by exploiting the results of Uhlig on the simultaneous
reduction of two real quadratic forms. This systematic study allowed
us to have a fine understanding the geometry of the intersection of two quadric
surfaces. We are now able to determine all characteristics of the
intersection curve, that is its genus, its singular points, its
algebraic components and connected components, and all the links
between these components. When one exists, we find a rational
parameterization of the components of the curve. In this sense, our
algorithm is optimal. We also made some significant improvements on
the complexity of the radical expression of the coefficients of the
obtained parameterization. Our algorithm is near-optimal in the sense
that the coefficients of the parameterization contain at most one
unnecessary square root in their expression. Our algorithm is optimal in the
worst case, in the sense that for every type of intersection curve
(for example a regular quartic, or a cubic and line, or two conics),
there exist pairs of quadrics for which the number of square
roots in the expression of the coefficients is minimal.
Finally, we made a complete implementation of our algorithm in MuPAD
which allowed us to get previously unheard of performances, in
terms of running time and in terms of the simplicity of the
result.
Cette thèse présente un algorithme robuste et efficace du calcul
d'une forme paramétrée exacte de la courbe d'intersection de deux
quadriques définies par des équations implicites à coefficients rationnels. Pour la première fois, le
paramétrage que nous obtenons contient toutes les informations
topologiques de la courbe et est assez simple pour être exploité
dans des applications géométriques non triviales.
De nombreux progrès, dans différents domaines, ont été
nécessaires pour atteindre ce résultat. Nous avons réalisé une étude
exhaustive de tous les cas possibles d'intersection, d'abord dans
$\Pp^3(\C)$ en nous basant sur les travaux de Segre, puis dans $\Pp^3(\R)$
en exploitant les résultats d'Uhlig sur la réduction simultanée de
deux formes quadratiques réelles. Cette étude systématique nous a
permis de maîtriser complètement la géométrie inhérente à
l'intersection de deux quadriques. Nous sommes maintenant capables
de déterminer toutes les caractéristiques de la courbe
d'intersection, à savoir son genre, ses points singuliers, le nombre
de ses composantes algébriques et connexes, et les incidences entre
ces composantes. Quand il en existe, nous
trouvons un paramétrage rationnel des composantes de la courbe
d'intersection. En ce sens, notre algorithme est optimal.
Nous avons aussi fait des progrès significatifs sur la complexité de l'expression radicale des
coefficients du paramétrage obtenu.
Notre résultat est quasi-optimal dans le sens où les coefficients du paramétrage
de la courbe d'intersection que nous calculons contiennent au plus
une racine carrée non nécessaire dans leur expression.
De plus, notre résultat est optimal dans le cas le pire,
dans le sens où pour chaque type de courbe d'intersection
(par exemple une quartique régulière, ou une cubique et une droite, ou
deux coniques), il existe des paires de quadriques pour lesquelles le
nombre de racines carrées apparaissant dans l'expression des
coefficients de notre paramétrage est minimal.
Enfin, nous avons réalisé une implantation complète de notre
algorithme en MuPAD qui nous a permis d'afficher des
performances inédites, tant en terme de vitesse d'exécution qu'en terme de
simplicité du résultat obtenu.
d'une forme paramétrée exacte de la courbe d'intersection de deux
quadriques définies par des équations implicites à coefficients rationnels. Pour la première fois, le
paramétrage que nous obtenons contient toutes les informations
topologiques de la courbe et est assez simple pour être exploité
dans des applications géométriques non triviales.
De nombreux progrès, dans différents domaines, ont été
nécessaires pour atteindre ce résultat. Nous avons réalisé une étude
exhaustive de tous les cas possibles d'intersection, d'abord dans
$\Pp^3(\C)$ en nous basant sur les travaux de Segre, puis dans $\Pp^3(\R)$
en exploitant les résultats d'Uhlig sur la réduction simultanée de
deux formes quadratiques réelles. Cette étude systématique nous a
permis de maîtriser complètement la géométrie inhérente à
l'intersection de deux quadriques. Nous sommes maintenant capables
de déterminer toutes les caractéristiques de la courbe
d'intersection, à savoir son genre, ses points singuliers, le nombre
de ses composantes algébriques et connexes, et les incidences entre
ces composantes. Quand il en existe, nous
trouvons un paramétrage rationnel des composantes de la courbe
d'intersection. En ce sens, notre algorithme est optimal.
Nous avons aussi fait des progrès significatifs sur la complexité de l'expression radicale des
coefficients du paramétrage obtenu.
Notre résultat est quasi-optimal dans le sens où les coefficients du paramétrage
de la courbe d'intersection que nous calculons contiennent au plus
une racine carrée non nécessaire dans leur expression.
De plus, notre résultat est optimal dans le cas le pire,
dans le sens où pour chaque type de courbe d'intersection
(par exemple une quartique régulière, ou une cubique et une droite, ou
deux coniques), il existe des paires de quadriques pour lesquelles le
nombre de racines carrées apparaissant dans l'expression des
coefficients de notre paramétrage est minimal.
Enfin, nous avons réalisé une implantation complète de notre
algorithme en MuPAD qui nous a permis d'afficher des
performances inédites, tant en terme de vitesse d'exécution qu'en terme de
simplicité du résultat obtenu.
Mots clés
calcul formel et manipulations algébriques<br />Algorithmes <br />informatique graphique<br />géométrie algorithmique et modélisation<br />géométrique.
calcul formel et manipulations algébriques<br />Algorithmes <br />informatique graphique<br />géométrie algorithmique et modélisation<br />géométrique
Domaines
Génie logiciel [cs.SE]
Loading...