Arrangement Computation for Planar Algebraic Curves

real planar algebraic curves. Our algorithm provides a geometric-topological
analysis of the decomposition of the plane induced by a finite number
of algebraic curves in terms of a cylindrical algebraic decomposition of
the plane. Compared to previous approaches, we improve in two main aspects:
Firstly, we significantly limit the types of involved exact operations,
that is, our algorithms only use resultant and GCD computations
as purely symbolic operations. Secondly, we introduce a new hybrid method in the
lifting step of our algorithm which combines the use of a certified numerical
complex root solver and information derived from the resultant computation.
Additionally, we never consider any coordinate transformation and the output
is also given with respect to the initial coordinate system.

We implemented our algorithm as a prototypical package of the C++-library
CGAL. Our implementation exploits graphics hardware to expedite the
resultant and GCD computation. We also compared our implementation with the current
reference implementation, that is, CGAL's curve analysis and
arrangement for algebraic curves. For various
series of challenging instances, our experiments show that the new
implementation outperforms the existing one.