Robust algebraic methods for geometric computing

Abstract

Geometric 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.

Οι γεωμετρικοί υπολογισμοί στην περιοχή της σχεδίασης με τη βοήθεια υπολογιστή (CAGD) και τη μοντελοποίηση στερεών απαιτούν την επίλυση μη γραμμικών πολυωνυμικών συστημάτων με τρόπο που να παρέχει πιστοποιημένα αποτελέσματα, έστω και προσεγγιστικά. Παρουσιάζουμε νέους αλγορίθμους υποδιαίρεσης που αντιμετωπίζουν αυτό το θεμελιώδες πρόβλημα. Συγκεκριμένα, γενικεύουμε τον αλγόριθμο επίλυσης που βασίζεται σε συνεχόμενα κλάσματα (αρχικά σχεδιασμένο για μονομεταβλητά πολυώνυμα) ώστε να εφαρμόζεται σε χώρους οποιασδήποτε διάστασης. Χρησιμοποιούμε ταχείες συναρτήσεις φραγής, ελέγχους μοναδικότητας, προβολή και προ-εξομάλυνση (preconditioning) για την επιτάχυνση της σύγκλισης. Πέρα από τα πρακτικά πειράματα, παρέχουμε θεωρητικές εκτιμήσεις υπολογιστικής πολυπλοκότητας (σε επίπεδο bit), καθώς και φράγματα στο μοντέλο πραγματικής μνήμης RAM, με τη χρήση αριθμών κατάστασης (condition numbers) για πραγματικούς αριθμούς. Ένα βασικό εμπόδιο για κάθε μέθοδο επίλυσης στο πεδίο των πραγματικών αριθμών είναι τα ιδιάζοντα μεμονωμένα σημεία. Χρησιμοποιούμε τοπικά αντίστροφα συστήματα και πιστοποιημένους αριθμητικούς υπολογισμούς για να καθορίσουμε κριτήρια πιστοποίησης που επιτρέπουν τη διαχείριση ιδιαζουσών λύσεων. Με αυτόν τον τρόπο, μπορούμε να ελέγξουμε την ύπαρξη και τη μοναδικότητα ιδιομορφιών με συγκεκριμένη δομή πολλαπλότητας, χρησιμοποιώντας μεθόδους επαλήθευσης που βασίζονται στην αριθμητική διαστημάτων και σε θεωρήματα σταθερού σημείου. Εξετάζουμε δύο σημαντικές γεωμετρικές εφαρμογές. Πρώτον, την προσέγγιση επίπεδων ημι-αλγεβρικών συνόλων, τα οποία εμφανίζονται συχνά στην επίλυση γεωμετρικών προβλημάτων με περιορισμούς. Παρουσιάζουμε έναν αποδοτικό αλγόριθμο για τον εντοπισμό συνεκτικών συνιστωσών και, για δεδομένο επίπεδο ακρίβειας, για τον υπολογισμό μιας πολυγωνικής και ισοτοπικής προσέγγισης του ακριβούς συνόλου. Δεύτερον, παρουσιάζουμε ένα αλγεβρικό πλαίσιο για τον υπολογισμό γενικευμένων διαγραμμάτων Voronoi, το οποίο είναι εφαρμόσιμο σε κάθε τύπο διαγράμματος όπου η απόσταση από ένα σημείο-πηγή (site) μπορεί να εκφραστεί μέσω μιας διμεταβλητής πολυωνυμικής συνάρτησης (π.χ. ανισότροπα διαγράμματα, διαγράμματα ισχύος κ.λπ.). Στις περιπτώσεις όπου αυτό δεν είναι εφικτό (π.χ. διάγραμμα Apollonius, διάγραμμα Voronoi ελλείψεων κ.ά.), επεκτείνουμε τη θεωρία ώστε να καλύπτει συναρτήσεις απόστασης που ορίζονται με έμμεσο τρόπο (implicit).

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 des 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 ellipses etc), nous étendons la théorie aux distances implicitement données.