Computing curve intersection by means of simultaneous iterations. A new algorithm is proposed for computing the intersection of two plane curves given in rational parametric form [the general solution steps are described by J. Hoschek and D. Lasser, Fundamentals of computer aided geometric design (1993; Zbl 0788.68002)]. This approach avoids symbolic manipulations and is completely numerical. It relies on the Ehrlich-Aberth iteration complemented with some computational tools like the properties of Sylvester and Bézout matrices, a stopping criterion based on the concept of pseudo-zero, an inclusion result and the choice of initial approximations based on the Newton polygon. The algorithm is implemented as a Fortran 95 module. From the numerical experiments performed with a wide set of test problems it shows a better robustness and stability with respect to the Manocha-Demmel approach based on eigenvalue computation. In fact, the algorithm provides better approximations in terms of the relative error and performs successfully in many critical cases where the eigenvalue computation fails.
Keywords for this software
References in zbMATH (referenced in 6 articles , 1 standard article )
Showing results 1 to 6 of 6.
- Winkler, Joab R.; Halawani, Hanan: The Sylvester and Bézout resultant matrices for blind image deconvolution (2018)
- Bourne, Martin; Winkler, Joab R.; Yi, Su: The computation of the degree of an approximate greatest common divisor of two Bernstein polynomials (2017)
- Noferini, Vanni; Townsend, Alex: Numerical instability of resultant methods for multidimensional rootfinding (2016)
- Iwata, Satoru; Nakatsukasa, Yuji; Takeda, Akiko: Computing the signed distance between overlapping ellipsoids (2015)
- Nakatsukasa, Yuji; Noferini, Vanni; Townsend, Alex: Computing the common zeros of two bivariate functions via Bézout resultants (2015)
- Bini, Dario A.; Marco, Ana: Computing curve intersection by means of simultaneous iterations (2006)