Exact, efficient, and complete arrangement computation for cubic curves

DOI10.1016/J.COMGEO.2005.10.003MaRDI QIDQ2507159zbMATH OpenOpenAlexFDO

Authors Arno Eigenwillig, Lutz Kettner, Elmar Schömer, Nicola Wolpert

Publication date 10 October 2006

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL http://edoc.mpg.de/314461

algebraic curves arrangements cubic curves exact geometric computation numerical examples robustness sweep-line algorithm

Mathematics Subject Classification ID

Computational aspects of algebraic curves (14Q05) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Review text

This detailed paper solves the problem of computing arrangements of cubic curves with an adapted Bentley-Ottmann sweep-line method. The authors emphasize exactness (e.g.\ differentiating between tangential intersection and two very close transverse intersections), efficiency (i.e., capability to handle large sets of data), and completeness. The sweep-line algorithm requires the computation of single-curve event points and two-curve event points, and their lexicographic comparison. This entails finding isolating intervals for all event coordinates. Analysis of events uses various resultants and auxiliary curves -- a separate discussion of each conceivable case is required, and no attempt is made here to describe the individual solutions. As the proposed algorithm aborts if genericity assumptions are violated (there are up to 279 forbidden directions of an \(y\) axis for each analyzed curved pair), it is augmented by random shearing. Separate attention is given to the ordering of curve segments passing through a single event point, which is done in linear time, thus yielding a runtime not greater than other instances of the sweep algorithm (in the Real RAM model). The paper concludes with experiments of both random and degenerate input data, consisting of up to 200 curves and resulting in up to 500.000 half-edges.

Recommendations

Cites work

Cited in

(13)

Describes a project that uses

Uses Software

This page was built for publication: Exact, efficient, and complete arrangement computation for cubic curves

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2507159)