Abstract
dc:descriptionGeometric computation in computer aided geometric design and solid modeling calls for solving non-linear polynomial systems in an approximate-yetcertified 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 from practical experiments, we provide theoretical bit complexity estimates, as well as bounds in the real RAM model, by means of real condition numbers. A main 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.
Degree
thesis:*- Grantor dc:publisher
- Institutes outside Greece
- Year dc:date
- 2011
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Mantzaflaris, Angelos
- Μαντζαφλάρης, Άγγελος
Subjects
dc:subject × 34- Αλγόριθμος υποδιαίρεσης
- Διάγραμμα Voronoi
- Ημι-αλγεβρικό σύνολο
- Διάταξη καμπυλών
- Αποπληθωρισμός ριζών
- Μεμονωμένο ιδιάζον σημείο
- Συνεχή κλάσματα
- Απομόνωση ριζών
- Subdivision algorithm
- Voronoi diagram
- Semi-algebraic set
- Arrangement of curves
- Root deflation
- Singular isolated point
- Continued fractions
- Root isolation
- Isolation des racines
- Diagramme de Voronoi
- Ensemble semi-algébrique
- Arrangement des courbes
- Déflation de racine
- Point singulier isolé
- Fractions continues
- Algorithme de sous-division
- Μαθηματικά
- Φυσικές Επιστήμες
- Υπολογιστικά μαθηματικά
- Επιστήμη Ηλεκτρονικών Υπολογιστών και Πληροφορική
- Γραφικά υπολογιστή και Σχεδιασμός με χρήση υπολογιστή
- Mathematics
- Natural Sciences
- Computational Mathematics
- Computer and Information Sciences
- Computer Graphics and Computer-Aided Design
Rights
- Language dc:language
- eng
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/62803