Reduced difference polynomials and self-intersection computations

Rida T. Farouki

Applied Mathematics and Computation, 2018, vol. 324, issue C, 174-190

Abstract: A reduced difference polynomialf(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 ]2 can be determined from those of p(t) through a simple algorithm, and can be restricted to any subdomain of [ 0, 1 ]2 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 ]2 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.

Keywords: Bernstein basis; Polynomial division; Variation-diminishing property; Quadtree decomposition; Self-intersections; Offset curve trimming (search for similar items in EconPapers)
Date: 2018
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300317308755
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:324:y:2018:i:c:p:174-190

DOI: 10.1016/j.amc.2017.12.016

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().