# Item

ITEM ACTIONSEXPORT

Released

Book Chapter

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

##### External Resource

No external resources are shared

##### Fulltext (restricted access)

There are currently no full texts shared for your IP range.

##### Fulltext (public)

There are no public fulltexts stored in PuRe

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Wolpert, N. (2003). Jacobi Curves: Computing the Exact Topology of Arrangements of
Non-Singular Algebraic Curves. In *Algorithms - ESA 2003* (pp. 532-543). Berlin: Springer.

Cite as: https://hdl.handle.net/11858/00-001M-0000-0019-EBB5-3

##### Abstract

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. Our algorithm
is output-sensitive in the sense that the algebraic
effort we need for sweeping a tangential intersection
point depends on its multiplicity.