Skip to main content
Open Access Publications from the University of California

Reduced difference polynomials and self-intersection computations


© 2017 Elsevier Inc. 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]2can be determined from those of p(t) through a simple algorithm, and can be restricted to any subdomain of [0, 1]2by 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]2guided 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.

Many UC-authored scholarly publications are freely available on this site because of the UC Academic Senate's Open Access Policy. Let us know how this access is important for you.

Main Content
Current View