A certified numerical algorithm for the topology of resultant and discriminant curves

Rémi Imbach 1 Guillaume Moroz 1 Marc Pouget 1
1 VEGAS - Effective Geometric Algorithms for Surfaces and Visibility
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
Abstract : Let C be a real plane algebraic curve defined by the resultant of two polynomials (resp. by the discriminant of a polynomial). Geometrically such a curve is the projection of the intersection of the surfaces $P(x, y, z) = Q(x, y, z) = 0 (resp. P(x, y, z) = ∂P ∂z (x, y, z) = 0)$, and generically its singularities are nodes (resp. nodes and ordinary cusps). State-of-the-art numerical algorithms compute the topology of smooth curves but usually fail to certify the topology of singular ones. The main challenge is to find practical numerical criteria that guarantee the existence and the uniqueness of a singularity inside a given box B, while ensuring that B does not contain any closed loop of C. We solve this problem by first providing a square deflation system, based on subresultants, that can be used to certify numerically whether B contains a unique singularity p or not. Then we introduce a numeric adaptive separation criterion based on interval arithmetic to ensure that the topology of C in B is homeomorphic to the local topology at p. Our algorithms are implemented and experiments show their efficiency compared to state-of-the-art symbolic or homotopic methods.
Type de document :
Article dans une revue
Journal of Symbolic Computation, Elsevier, 2016, 80, Part 2, pp.285--306. 〈10.1016/j.jsc.2016.03.011〉
Liste complète des métadonnées

Littérature citée [46 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01402194
Contributeur : Marc Pouget <>
Soumis le : jeudi 24 novembre 2016 - 13:18:50
Dernière modification le : vendredi 25 novembre 2016 - 15:22:19
Document(s) archivé(s) le : lundi 20 mars 2017 - 19:24:45

Fichier

topo_res_disc2.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Rémi Imbach, Guillaume Moroz, Marc Pouget. A certified numerical algorithm for the topology of resultant and discriminant curves. Journal of Symbolic Computation, Elsevier, 2016, 80, Part 2, pp.285--306. 〈10.1016/j.jsc.2016.03.011〉. 〈hal-01402194〉

Partager

Métriques

Consultations de
la notice

345

Téléchargements du document

31