3532 articles – 5253 Notices  [english version]

inria-00517175, version 1

On the topology of real algebraic plane curves

Jinsan Cheng 1, Sylvain Lazard () 2, Luis Mariano Peñaranda () 2, Marc Pouget () 2, Fabrice Rouillier () 34, Elias P. P. Tsigaridas () 5

Mathematics in Computer Science 4, 1 (2010) 113-137

Résumé : 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.

  • 1 :  Key Laboratory of Mathematics Mechanization (KLMM)
  • Chinese Academy of Science (CAS) – Academy of Mathematics and Systems Science (AMSS), China – Institute of Systems Science (ISS), China
  • 2 :  VEGAS (INRIA Lorraine - LORIA)
  • INRIA – CNRS : UMR7503 – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine (INPL)
  • 3 :  SALSA (INRIA Rocquencourt)
  • INRIA – CNRS : UMR7606 – Université Pierre et Marie Curie [UPMC] - Paris VI
  • 4 :  Laboratoire d'Informatique de Paris 6 (LIP6)
  • CNRS : UMR7606 – Université Pierre et Marie Curie [UPMC] - Paris VI
  • 5 :  Department of Computer Science [Aarhus]
  • University of Aarhus
  • Domaine : Informatique/Géométrie algorithmique
 
  • inria-00517175, version 1
  • oai:hal.inria.fr:inria-00517175
  • Contributeur : 
  • Soumis le : Lundi 13 Septembre 2010, 17:01:39
  • Dernière modification le : Jeudi 10 Mars 2011, 16:04:12