Elias' Article

On the topology of planar algebraic curves.
Jinsan Chen, Sylvain Lazard, Luis Pe naranda, Marc Pouget, Fabrice Rouillier, and Elias P. Tsigaridas.
Mathematics for Computer Science. Special issue on Computational Geometry and Computer Aided Geometric Design, 4(1):113–137, Birkhäuser Basel, 2010.

• Home
• Research
• Teaching
• Contact

Files:

[PDF] 348.0kB  [gzipped postscript] 319.6kB  

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 use sub-resultant sequences and computations with polynomials with algebraic coefficients. A novelty of our approach is to replace these tools by Gröbner 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 non-generic curves.

@Article{clpprt-mcs-2010,
  author =       {Jinsan Chen and Sylvain Lazard and Luis
                  Pe{\~n}aranda and Marc Pouget and Fabrice Rouillier
                  and Elias~P. Tsigaridas},
  title =        {On the topology of planar algebraic curves},
  journal =      "Mathematics for Computer Science.  Special issue on
                  Computational Geometry and Computer Aided Geometric
                  Design",
  publisher =    {Birkh\"auser Basel},
  issn =         {1661-8270},
  pages =        {113-137},
  volume =       4,
  number =       1,
  year =         2010,
  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 use
                  sub-resultant sequences and computations with
                  polynomials with algebraic coefficients.  A novelty
                  of our approach is to replace these tools by
                  Gr{\"o}bner 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 non-generic curves.",
}

Generated by bib2html.pl (written by Patrick Riley , modified by Elias ) on Wed Oct 23, 2019 21:41:02