Exact Algebraic and Geometric Computations for Parametric Curves
Calculs algébriques et géométriques exacts pour les courbes paramétriques
Résumé
This thesis proposes algorithms for solving non-linear computational geometry problems related to parametric curves. Specifically, it focuses on computing the topology of curves in ℝⁿ and the convex hull of curves in ℝ^2 and ℝ^3, without resorting to implicitization. The algorithms perform exact computations with real algebraic numbers through separation bounds and interval arithmetic. For the topology computation, the proposed algorithm works for curves in any dimension and computes an abstract graph that is isotopic to the curve in the embedding space. The bit-complexity is analyzed and found to be linear in the dimension of the ambient space. For the convex hull computation, the thesis presents algorithms for plane and space curves. The convex hull is a semi-algebraic set and an exact representation of its boundary is obtained through a combination of line segments and arcs of the curve for the 2D case, and of triangles and surface patches for the 3D case. The boundary description is computed for each case along with bit-complexity estimates. The computation reduces to univariate and bivariate solving and to isolating roots of a univariate polynomial with coefficients in a multiple algebraic field extension. To provide asymptotic upper bounds for the convex hull problem, the thesis provides bit-complexity bounds for the root isolation of a polynomial F ∈ L[Y], where L is a multiple algebraic extension of ℚ. Aggregate bounds for the separation of the roots of F are employed and two algorithmic solutions are présente; a formal one based on Rational Univariate Representations and a numerical one that is also certified.
Cette thèse propose des algorithmes pour résoudre des problèmes de géométrie computationnelle non linéaire liés aux courbes paramétriques. Elle se concentre spécifiquement sur le calcul de la topologie des courbes dans ℝⁿ et de l'enveloppe convexe des courbes dans ℝ^2 et ℝ^3, sans avoir recours à l'implicitation. Les algorithmes effectuent des calculs exacts avec des nombres réels grâce à des bornes de séparation et à l'arithmétique des intervalles. Pour le calcul de la topologie, l'algorithme proposé fonctionne pour des courbes de n'importe quelle dimension et calcule un graphe abstrait qui est isotopique à la courbe dans l'espace de plongement. La complexité binaire est analysée et trouvée pour être linéaire dans la dimension de l'espace ambiant. Pour le calcul de l'enveloppe convexe, la thèse présente des algorithmes pour les courbes planes et les courbes spatiales. L'enveloppe convexe est un ensemble semi-algébrique et une représentation exacte de sa frontière est obtenue par une combinaison de segments de droite et d'arcs de la courbe pour le cas en 2D, et de triangles et de patchs de surface pour le cas en 3D. La description de la frontière est calculée pour chaque cas ainsi que des estimations de la complexité binaire. Le calcul se réduit à la résolution univariée et bivariée et à l'isolement des racines d'un polynôme univarié avec des coefficients dans une extension de corps multiple. Pour fournir des bornes supérieures asymptotiques pour le problème de l'enveloppe convexe, la thèse fournit des bornes de complexité binaire pour l'isolement des racines d'un polynôme F ∈ L[Y], où L est une extension algébrique multiple de ℚ. Des bornes amorties sur la séparation des racines de F sont utilisées et deux solutions algorithmiques sont présentées; une formelle, qui est basée sur la représentation rationnelle univariée, et une solution numérique, qui est également certifiée.
Origine : Version validée par le jury (STAR)