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

Wolpert, Nicola

doi:10.1007/978-3-540-39658-1_49

アイテム詳細

登録内容を編集ファイル形式で保存

一時保存へ追加

タグ情報を表示リリース履歴を表示詳細要約

公開

書籍の一部

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

There are no locators available

Fulltext (restricted access)

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

フルテキスト (公開)

公開されているフルテキストはありません

付随資料 (公開)

There is no public supplementary material available

引用

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.

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

要旨

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.