On the topology of planar algebraic curves

Jinsan Cheng 1 Sylvain Lazard 1 Luis Peñaranda 1 Marc Pouget 1 Fabrice Rouillier 2 Elias P. Tsigaridas 3
1 VEGAS - Effective Geometric Algorithms for Surfaces and Visibility
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
2 SALSA - Solvers for Algebraic Systems and Applications
LIP6 - Laboratoire d'Informatique de Paris 6, Inria Paris-Rocquencourt
3 GALAAD - Geometry, algebra, algorithms
CRISAM - Inria Sophia Antipolis - Méditerranée , UNS - Université Nice Sophia Antipolis, CNRS - Centre National de la Recherche Scientifique : UMR6621
Abstract : We revisit the problem of computing the topology and geometry of a real algebraic plane curve. The topology is of prime interest but geometric information, such as the position of singular and critical points, is also relevant. A challenge is to compute efficiently this information for the given coordinate system even if the curve is not in generic position. Previous methods based on the cylindrical algebraic decomposition (CAD) use sub-resultant sequences and computations with polynomials with algebraic coefficients. A novelty of our approach is to replace these tools by Groebner basis computations and isolation with rational univariate representations. This has the advantage of avoiding computations with polynomials with algebraic coefficients, even in non-generic positions. Our algorithm isolates critical points in boxes and computes a decomposition of the plane by rectangular boxes. This decomposition also induces a new approach for computing an arrangement of polylines isotopic to the input curve. We also present an analysis of the complexity of our algorithm. An implementation of our algorithm demonstrates its efficiency, in particular on high-degree nongeneric curves.
Type de document :
Communication dans un congrès
John Hershberger and Efi Fogel. 25th annual symposium on Computational geometry - SCG 2009, Jun 2009, Aarhus, Denmark. ACM, pp.361--370, 2009, 〈http://portal.acm.org/citation.cfm?doid=1542362.1542424〉. 〈10.1145/1542362.1542424〉
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00425383
Contributeur : Marc Pouget <>
Soumis le : jeudi 12 novembre 2009 - 19:44:51
Dernière modification le : mardi 10 octobre 2017 - 13:46:49
Document(s) archivé(s) le : mardi 16 octobre 2012 - 12:31:32

Fichier

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

Identifiants

Collections

Citation

Jinsan Cheng, Sylvain Lazard, Luis Peñaranda, Marc Pouget, Fabrice Rouillier, et al.. On the topology of planar algebraic curves. John Hershberger and Efi Fogel. 25th annual symposium on Computational geometry - SCG 2009, Jun 2009, Aarhus, Denmark. ACM, pp.361--370, 2009, 〈http://portal.acm.org/citation.cfm?doid=1542362.1542424〉. 〈10.1145/1542362.1542424〉. 〈inria-00425383〉

Partager

Métriques

Consultations de
la notice

435

Téléchargements du document

185