English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
 Local TagsRelease HistoryDetailsSummary
  Jacobi Curves: Computing the Exact Topology of Arrangements of Non-Singular Algebraic Curves

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.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-0019-EBB5-3 Version Permalink: https://hdl.handle.net/11858/00-001M-0000-0019-EBBF-F
Genre: Book Chapter

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Wolpert, Nicola1, Author           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 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.

Details

show
hide
Language(s): eng - English
 Dates: 2003
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: DOI: 10.1007/978-3-540-39658-1_49
BibTex Citekey: w-jccetansal-03
 Degree: -

Event

show

Legal Case

show

Project information

show

Source 1

show
hide
Title: Algorithms - ESA 2003
  Subtitle : 11th Annual European Symposium, Budapest, Hungary, September 16-19, 2003. Proceedings
  Abbreviation : ESA 2003
Source Genre: Proceedings
 Creator(s):
Affiliations:
Publ. Info: Berlin : Springer
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 532 - 543 Identifier: -

Source 2

show
hide
Title: Lecture Notes in Computer Science
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: 2832 Sequence Number: - Start / End Page: - Identifier: -