Exact and efficient 2D-arrangements of arbitrary algebraic curves

Abstract

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