Exact and Efficient 2D-Arrangements of Arbitrary Algebraic Curves

We show how to compute the planar arrangement induced by segments
of arbitrary algebraic curves with the Bentley-Ottmann sweep-line
algorithm. The necessary geometric primitives reduce to cylindrical
algebraic decompositions of the plane for one or two curves.
We compute them by a new and efficient method that combines
adaptive-precision root finding (the Bitstream Descartes method of
Eigenwillig et~al.,\ 2005) with a small number of symbolic
computations, and that delivers the exact result in all cases.
Thus we obtain an algorithm which produces the mathematically true
arrangement, undistorted by rounding error, for any set of input
segments.
Our algorithm is implemented in the EXACUS library AlciX.
We report on experiments; they indicate the efficiency of our approach.