Reduced difference polynomials and self-intersection computations
- Author(s): Farouki, RT
- et al.
Published Web Locationhttps://doi.org/10.1016/j.amc.2017.12.016
A reduced difference polynomial f(u,v)=(p(u)−p(v))/(u−v) may be associated with any given univariate polynomial p(t), t ∈ [0, 1] such that the locus f(u,v)=0 identifies the pairs of distinct values u and v satisfying p(u)=p(v). The Bernstein coefficients of f(u, v) on [0, 1] can be determined from those of p(t) through a simple algorithm, and can be restricted to any subdomain of [0, 1] by standard subdivision methods. By constructing the reduced difference polynomials f(u, v) and g(u, v) associated with the coordinate components of a polynomial curve r(t)=(x(t),y(t)), a quadtree decomposition of [0, 1] guided by the variation-diminishing property yields a numerically stable scheme for isolating real solutions of the system f(u,v)=g(u,v)=0, which identify self-intersections of the curve r(t). Through the Kantorovich theorem for guaranteed convergence of Newton–Raphson iterations to a unique solution, the self-intersections can be efficiently computed to machine precision. By generalizing the reduced difference polynomial to encompass products of univariate polynomials, the method can be readily extended to compute the self-intersections of rational curves, and of the rational offsets to Pythagorean–hodograph curves. 2 2 2