Robust algebraic methods for geometric computing / par Angelos Mantzaflaris ; sous la direction de Bernard Mourrain

Date :

Editeur / Publisher : [S.l.] : [s.n.] , 2011

Type : Livre / Book

Type : Thèse / Thesis

Langue / Language : anglais / English

Catalogue Worldcat

Racines d'un nombre

Fractions continues

Ensembles semi-algébriques

Voronoi, Polygones de

Mourrain, Bernard (19..-....) (Directeur de thèse / thesis advisor)

Université de Nice (1965-2019) (Organisme de soutenance / degree-grantor)

Université de Nice-Sophia Antipolis. Faculté des sciences (Organisme de soutenance / degree-grantor)

École doctorale Sciences et technologies de l'information et de la communication (Sophia Antipolis, Alpes-Maritimes) (Organisme de soutenance / degree-grantor)

Relation : Robust algebraic methods for geometric computing / par Angelos Mantzaflaris ; sous la direction de Bernard Mourrain / Lille : Atelier national de reproduction des thèses , 2011

Résumé / Abstract : Le calcul géométrique en modélisation et en CAO nécessite la résolution approchée, et néanmoins certifiée, de systèmes polynomiaux. Nous introduisons de nouveaux algorithmes de sous-division afin de résoudre ce problème fondamental, calculant des développements en fractions continues des coordonnées des solutions. Au-delà des exemples concrets, nous fournissons des estimations de la complexité en bits et des bornes dans le modèle de RAM réelle. La difficulté principale de toute méthode de résolution consiste en les points singuliers isolés. Nous utilisons les systèmes locaux inverses et des calculs numériques certifiés afin d’obtenir un critère de certification pour traiter les solutions singulières. Ce faisant, nous sommes en mesure de vérifier l’existence et l’unicité des singularités d’une structure de multiplicité donnée. Nous traitons deux principales applications géométriques. La première : l’approximation des ensembles semi-algébriques plans, apparaît fréquemment dans la résolution de contraintes géométriques. Nous présentons un algorithme efficace pour identifier les composants connexes et pour calculer les approximations polygonales et isotopiques à l’ensemble exact. Dans un deuxième temps, nous présentons un cadre algébrique afin de calculer des diagrammes de Voronoi. Celui-ci sera applicable à tout type de diagramme dans lequel la distance à partir d’un site peut être exprimé par une fonction polynomiale à deux variables (anisotrope, diagramme de puissance, etc.) Si cela n’est pas possible (par exemple diagramme de Apollonius, VD des éclipses etc.), nous étendons la théorie aux distances implicitement données.

Résumé / Abstract : Geometric computation in computer aided geometric design and solid modelling calls for solving non-linear polynomial systems in an approximate-yet-certified manner. We introduce new subdivision algorithms that tackle this fundamental problem. In particular, we generalize the univariate so-called continued fraction solver to general dimension. Fast bounding functions, unicity tests projection and preconditioning are employed to speed up convergence. Apart for practical experiments, we provide theoretical bit complexity estimates, as well as bounds in the real RAM model, by means of real condition numbers. A man bottleneck for any real solving method is singular isolated points. We employ local inverse systems and certified numerical computations, to provide certification criteria to treat singular solutions. In doing so, we are able to check existence and uniqueness of singularities of a given multiplicity structure using verification methods, based on interval arithmetic and fixed point theorems. Two major geometric applications are undertaken. First, the approximation of planar semi-algebraic sets, commonly occurring in constraint geometric solving. We present an efficient algorithm to identify connected components and, for a given precision, to compute polygonal and isotopic approximation of the exact set Second, we present an algebraic framework to compute generalized Voronoï diagrams, that is applicable to any diagram type in which the distance from a site can be expressed by a bi-variate polynomial function (anisotropic, power diagram etc.) In cases where this is not possible (eg. Apollonius diagram, VD of ellipses and so on), we extend the theory to implicitly given distance functions.