Exact and Efficient 2D-Arrangements of Arbitrary Algebraic Curves

Eigenwillig, Arno; Kerber, Michael

Item

ITEM ACTIONSEXPORT

Add to Basket

Local TagsRelease HistoryDetailsSummary

Released

Conference Paper

Exact and Efficient 2D-Arrangements of Arbitrary Algebraic Curves

MPS-Authors

/persons/resource/persons44369

Eigenwillig, Arno
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons44759

Kerber, Michael
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

Eigenwillig, A., & Kerber, M. (2008). Exact and Efficient 2D-Arrangements of Arbitrary Algebraic Curves. In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 122-131). New York, NY: ACM.

Cite as: https://hdl.handle.net/11858/00-001M-0000-000F-1B8F-4

Abstract

We show how to compute the planar arrangement induced by segments of arbitrary algebraic curves with the Bentley-Ottmann sweep-line algorithm. The necessary geometric primitives reduce to cylindrical algebraic decompositions of the plane for one or two curves. We compute them by a new and efficient method that combines adaptive-precision root finding (the Bitstream Descartes method of Eigenwillig et~al.,\ 2005) with a small number of symbolic computations, and that delivers the exact result in all cases. Thus we obtain an algorithm which produces the mathematically true arrangement, undistorted by rounding error, for any set of input segments. Our algorithm is implemented in the EXACUS library AlciX. We report on experiments; they indicate the efficiency of our approach.