English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Book Chapter

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

MPS-Authors
/persons/resource/persons45758

Wolpert,  Nicola
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

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.