Search

New differential-recurrence relations for B-spline basis functions are given. Using these relations, a recursive method for finding the Bernstein-B\'{e}zier coefficients of B-spline basis functions over a single knot span is proposed. The algorithm works for any knot sequence and has an asymptotically optimal computational complexity. Numerical experiments show that the new method gives results which preserve a high number of digits when compared to an approach which uses the well-known de Boor-Cox formula.

New geometric methods for fast evaluation of derivatives of polynomial and rational B\'{e}zier curves are proposed. They apply an algorithm for evaluating polynomial or rational B\'{e}zier curves, which was recently given by the authors. Numerical tests show that the new approach is more efficient than the methods which use the famous de Casteljau algorithm. The algorithms work well even for high-order derivatives of rational B\'{e}zier curves of high degrees.

A new differential-recurrence relation for the B-spline functions of the same degree is proved. From this relation, a recursive method of computing the coefficients of B-spline functions of degree $m$ in the Bernstein-B\'{e}zier form is derived. Its complexity is proportional to the number of coefficients in the case of coincident boundary knots. This means that, asymptotically, the algorithm is optimal. In other cases, the complexity is increased by at most $O(m^3)$. When the Bernstein-B\'{e}zier coefficients of B-spline basis functions are known, it is possible to compute any B-spline function in linear time with respect to its degree by performing the geometric algorithm proposed recently by the authors. This algorithm scales well when evaluating the B-spline curve at multiple points, e.g., in order to render it, since one only needs to find the coefficients for each knot span once. When evaluating many B-spline curves at multiple points (as is the case when rendering tensor product B-spline surfaces), such approach has lower computational complexity than using the de Boor-Cox algorithm. The numerical tests show that the new method is efficient. The problem of finding the coefficients of the B-spline functions in the power basis can be solved similarly.

Dual Bernstein polynomials find many applications in approximation theory, computational mathematics, numerical analysis and computer-aided geometric design. In this context, one of the main problems is fast and accurate evaluation both of these polynomials and their linear combinations. New simple recurrence relations of low order satisfied by dual Bernstein polynomials are given. In particular, a first-order non-homogeneous recurrence relation linking dual Bernstein and shifted Jacobi orthogonal polynomials has been obtained. When used properly, it allows to propose fast and numerically efficient algorithms for evaluating all $n+1$ dual Bernstein polynomials of degree $n$ with $O(n)$ computational complexity.

A new algorithm for computing a point on a polynomial or rational curve in B\'{e}zier form is proposed. The method has a geometric interpretation and uses only convex combinations of control points. The new algorithm's computational complexity is linear with respect to the number of control points and its memory complexity is $O(1)$. Some remarks on similar methods for surfaces in rectangular and triangular B\'{e}zier form are also given.

New differential-recurrence properties of dual Bernstein polynomials are given which follow from relations between dual Bernstein and orthogonal Hahn and Jacobi polynomials. Using these results, a fourth-order differential equation satisfied by dual Bernstein polynomials has been constructed. Also, a fourth-order recurrence relation for these polynomials has been obtained; this result may be useful in the efficient solution of some computational problems.

In this paper, we present a new iterative approximate method of solving boundary value problems. The idea is to compute approximate polynomial solutions in the Bernstein form using least squares approximation combined with some properties of dual Bernstein polynomials which guarantee high efficiency of our approach. The method can deal with both linear and nonlinear differential equations. Moreover, not only second order differential equations can be solved but also higher order differential equations. Illustrative examples confirm the versatility of our method.

In the paper, we show that the transformations between modified Jacobi and Bernstein bases of the constrained space of polynomials of degree at most $n$ can be performed with the complexity $O(n^2)$. As a result, the algorithm of degree reduction of B\'ezier curves that was first presented in (Bhrawy et al., J. Comput. Appl. Math. 302 (2016), 369--384), and then corrected in (Lu and Xiang, J. Comput. Appl. Math. 315 (2017), 65--69), can be significantly improved, since the necessary transformations are done in those papers with the complexity $O(n^3)$. The comparison of running times shows that our transformations are also faster in practice.

In the paper, we give methods of construction of dual bases for the B-spline basis and truncated power basis. Explicit formulas for the dual B-spline basis are obtained using the Legendre-like orthogonal basis of the polynomial spline space presented in (Wei et al., Comput.-Aided Des. 45 (2013), 85-92) and a connection between orthogonal and dual bases of any space given in (Lewanowicz and Wo\'zny, J. Approx. Theory 138 (2006), 129-150). Construction of the dual truncated power basis is performed in two phases. We start with explicit formulas for the dual power basis of the space of polynomials. Then, we expand this basis using an iterative algorithm proposed in (Wo\'zny, J. Comput. Appl. Math. 260 (2014), 301-311). As a result, we obtain the dual truncated power basis. We also present some applications of the proposed dual polynomial spline bases and illustrative examples.

This paper deals with the problem of multi-degree reduction of a composite B\'ezier curve with the parametric continuity constraints at the endpoints of the segments. We present a novel method which is based on the idea of using constrained dual Bernstein polynomials to compute the control points of the reduced composite curve. In contrast to other methods, ours minimizes the $L_2$-error for the whole composite curve instead of minimizing the $L_2$-errors for each segment separately. As a result, an additional optimization is possible. Examples show that the new method gives much better results than multiple application of the degree reduction of a single B\'ezier curve.

In a recent paper (Appl. Math. Comput. 215, 1622--1645, 2009), the authors proposed a method of summation of some slowly convergent series. The purpose of this note is to give more theoretical analysis for this transformation, including the convergence acceleration theorem in the case of summation of generalized hypergeometric series. Some new theoretical results and illustrative numerical examples are given., Comment: revised version

In this paper, we give an efficient algorithm of degree reduction of B\'ezier curves with box constraints. The idea is to combine the previous iterative approach, that has been presented recently in (P. Gospodarczyk, Comput. Aided Des. 62 (2015), 143--151), with a fast method of construction of dual bases from (P. Wo\'zny, J. Comput. Appl. Math. 260 (2014), 301--311) and a new efficient method of modification of dual bases.

Dual Bernstein polynomials of one or two variables have proved to be very useful in obtaining B\'{e}zier form of the $L^2$-solution of the problem of best polynomial approximation of B\'{e}zier curve or surface. In this connection, the B\'{e}zier coefficients of dual Bernstein polynomials are to be evaluated at a reasonable cost. In this paper, a set of recurrence relations satisfied by the B\'{e}zier coefficients of dual bivariate Bernstein polynomials is derived and an efficient algorithm for evaluation of these coefficients is proposed. Applications of this result to some approximation problems of Computer Aided Geometric Design (CAGD) are discussed., Comment: arXiv admin note: text overlap with arXiv:1504.03557

We propose a novel approach to the problem of polynomial approximation of rational B\'ezier triangular patches with prescribed boundary control points. The method is very efficient thanks to using recursive properties of the bivariate dual Bernstein polynomials and applying a smart algorithm for evaluating a collection of two-dimensional integrals. Some illustrative examples are given.

We present an efficient method to solve the problem of the constrained least squares approximation of the rational B\'{e}zier curve by the B\'{e}zier curve. The presented algorithm uses the dual constrained Bernstein basis polynomials, associated with the Jacobi scalar product, and exploits their recursive properties. Examples are given, showing the effectiveness of the algorithm.

We present a new approach to the problem of $G^{k,l}$-constrained ($k,l \leq 3$) multi-degree reduction of B\'{e}zier curves with respect to the least squares norm. First, to minimize the least squares error, we consider two methods of determining the values of geometric continuity parameters. One of them is based on quadratic and nonlinear programming, while the other uses some simplifying assumptions and solves a system of linear equations. Next, for prescribed values of these parameters, we obtain control points of the multi-degree reduced curve, using the properties of constrained dual Bernstein basis polynomials. Assuming that the input and output curves are of degree $n$ and $m$, respectively, we determine these points with the complexity $O(mn)$, which is significantly less than the cost of other known methods. Finally, we give several examples to demonstrate the effectiveness of our algorithms.

In this paper, we present a novel approach to the problem of merging of B\'ezier curves with respect to the $L_2$-norm. We give illustrative examples to show that the solution of the conventional merging problem may not be suitable for further modification and applications. As in the case of the degree reduction problem, we apply the so-called restricted area approach -- proposed recently in (P. Gospodarczyk, Computer-Aided Design 62 (2015), 143--151) -- to avoid certain defects and make the resulting curve more useful. A method of solving the new problem is based on box-constrained quadratic programming approach.

This paper deals with the merging problem of segments of a composite B\'ezier curve, with the endpoints continuity constraints. We present a novel method which is based on the idea of using constrained dual Bernstein polynomial basis (P. Wo\'zny, S. Lewanowicz, Comput. Aided Geom. Design 26 (2009), 566--579) to compute the control points of the merged curve. Thanks to using fast schemes of evaluation of certain connections involving Bernstein and dual Bernstein polynomials, the complexity of our algorithm is significantly less than complexity of other merging methods.

Explicit formulae for the B\'ezier coefficients of the constrained dual Bernstein basis polynomials are derived in terms of the Hahn orthogonal polynomials. Using difference properties of the latter polynomials, efficient recursive scheme is obtained to compute these coefficients. Applications of this result to some problems of CAGD is discussed., Comment: 10 pages