Jacobi Curves: Computing the Exact Topology of Arrangements of Non-singular Algebraic Curves

摘要

We present an approach that extends the Bentley-Ottmann sweep-line algorithm to the exact computation of the topology of arrangements induced by non-singular algebraic curves of arbitrary degrees. Algebraic curves of degree greater than 1 are difficult to handle in case one is interested in exact and efficient solutions. In general, the coordinates of intersection points of two curves are not rational but algebraic numbers and this fact has a great negative impact on the efficiency of algorithms coping with them. The most serious problem when computing arrangements of non-singular algebraic curves turns out be the detection and location of tangential intersection points of two curves. The main contribution of this paper is a solution to this problem, using only rational arithmetic. We do this by extending the concept of Jacobi curves introduced in [11]. Our algorithm is output-sensitive in the sense that the algebraic effort we need for sweeping a tangential intersection point depends on its multiplicity.