Exact, efficient, and complete arrangement computation for cubic curves (Q2507159): Difference between revisions
From MaRDI portal
Changed an Item |
Changed an Item |
||
Property / describes a project that uses | |||
Property / describes a project that uses: EXACUS / rank | |||
Normal rank |
Revision as of 07:34, 29 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Exact, efficient, and complete arrangement computation for cubic curves |
scientific article |
Statements
Exact, efficient, and complete arrangement computation for cubic curves (English)
0 references
10 October 2006
0 references
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.
0 references
arrangements
0 references
algebraic curves
0 references
sweep-line algorithm
0 references
robustness
0 references
exact geometric computation
0 references
cubic curves
0 references
numerical examples
0 references