Robust Algebraic Curve Intersections with Tolerance Control

In this paper, a robust and efficient algorithm is proposed to calculate the intersection points of two planar algebraic curves with guaranteed tolerance. The proposed method takes advantage of the fundamental methods in the fields of CAGD, solution verification for nonlinear equations and symbolic computation. Specifically, the subdivision method is applied to quickly exclude the regions without intersection points, and then Krawczyk's method is used to find a sharp and guaranteed bound for the intersection points. For ill-conditional cases, Sturm's theorem is applied to determine if there are any intersection points in undetermined regions. We present examples to demonstrate the robustness and efficiency of our algorithm, and comparisons with classic methods and a state-of-the-art method are also provided. The method can be easily adapted to computing the intersection points of two parametric curves. (C)& nbsp;2022 Elsevier Ltd. All rights reserved.

Automated summary

In this paper, a robust and efficient algorithm is proposed for calculating the intersection points of two planar algebraic curves with guaranteed tolerance. The method combines fundamental techniques from the fields of CAGD, solution verification for nonlinear equations, and symbolic computation. The algorithm utilizes the subdivision method to quickly exclude regions without intersection points, and then employs Krawczyk's method and Sturm's theorem to determine the sharp and guaranteed bounds for intersection points. Examples and comparisons with other methods demonstrate the robustness and efficiency of the proposed algorithm, which can also be easily extended to compute intersection points of parametric curves.