@COMMENT {Autogenerated file by bib2html.pl version 0.94}
@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.",
}