6533b861fe1ef96bd12c4d3b
RESEARCH PRODUCT
Complete, exact, and efficient computations with cubic curves
Arno EigenwilligNicola WolpertLutz KettnerElmar Schömersubject
Discrete mathematicsModuli of algebraic curvesGeometric designConic sectionComputationFamily of curvesApplied mathematicsGravitational singularityAlgebraic curveSweep line algorithmMathematicsdescription
The Bentley-Ottmann sweep-line method can be used to compute thearrangement of planar curves provided a number of geometricprimitives operating on the curves are available. We discuss themathematics of the primitives for planar algebraic curves of degreethree or less and derive efficient realizations. As a result, weobtain a complete, exact, and efficient algorithm for computingarrangements of cubic curves. Conics and cubic splines are specialcases of cubic curves. The algorithm is complete in that it handles all possibledegeneracies including singularities. It is exact in that itprovides the mathematically correct result. It is efficient in thatit can handle hundreds of curves with a quarter million of segmentsin the final arrangement.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2004-06-08 | Proceedings of the twentieth annual symposium on Computational geometry |