Exact, efficient, and complete arrangement computation for cubic curves (Q2507159): Difference between revisions

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.