Deutsch
 
Benutzerhandbuch Datenschutzhinweis Impressum Kontakt
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Buchkapitel

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

MPG-Autoren
/persons/resource/persons45758

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

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

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.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-0019-EBB5-3
Zusammenfassung
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.