Evaluation of Gauss-Legendre curves Filip Chudy, Paweł Woźny Abstract We present new representations of Gauss–Legendre polynomials and their derivatives in the shifted power basis and in bases related to symmetric orthogonal Jacobi polynomials. Using these representations and certain recurrence relations, we propose efficient O ⁡ ( n 2 + d ​ n ) O(n^{2}+dn) methods for evaluating a Gauss–Legendre curve of degree n n in 𝔼 d \mathbb{E}^{d} . We also propose algorithms for multipoint evaluation with computational complexity O ⁡ ( M ​ d ​ n + d ​ n 2 ) O(Mdn+dn^{2}) , where M M is the number of evaluation points. 1 Introduction The Gauss–Legendre curves ( GL curves for short), recently introduced in [ 7 ] (see also [ 8 ] ), are polynomial parametric curves closely related to Gauss–Legendre quadratures and Legendre orthogonal polynomials (see, e.g., [ 2 ] , [ 6 ] ). They have recently started gaining traction in CAGD, partly due to their very good shape control properties. Unlike Bézier curves (see, e.g., [ 1 ] ), GL curves closely follow the control polygon, even at high degrees. Therefore, they may have many practical applications, for example in numerical analysis and computer graphics. However, the so-called Gauss–Legendre poly nomials ( GL polynomials for short), which form the basis of GL curves, are defined in a rather complicated manner, and their efficient evaluation is nontrivial. Note that the evaluation of points on GL curves is not discussed in [ 7 ] . The article is organized as follows. In Section 3 , we briefly describe the GL polynomials and GL curves and recall their main properties. The new representations of the GL polynomials and their derivatives are presented in Section 4 , where we consider expansions with respect to the shifted power basis and some orthogonal bases related to symmetric Jacobi polynomials (cf. § 2 ). Then, in Section 5 , using these representations, we propose fast and numerically stable algorithms for evaluating GL curves. Their computational complexity is O(n^{2}+dn) when computing a point on a GL curve of degree n\in\mathbb{N} in \mathbb{E}^{d} (d\geq 1) . Moreover, we investigate the problem of multipoint evaluation of GL curves and propose algorithms that run in O(Mdn+dn^{2}) time, where M denotes the number of evaluation points. Usually, M\gg n and d is small, so the computational complexity is O(Mdn) . Results of the conducted numerical experiments are presented in § 6 . 2 Symmetric Jacobi polynomials We now recall several well-known properties of orthogonal polynomials from the Jacobi family (of which the Legendre polynomials are a member) that will be useful in the study presented in this paper. For details and proofs of the results given below, we refer, for example, to [ 3 ] , [ 6 ] , [ 9 ] , and the references given therein. The Jacobi polynomials P^{(\alpha,\beta)}_{m}\in\Pi_{m}\setminus\Pi_{m-1} (m\in\mathbb{N};\,\alpha,\beta>-1) are orthogonal in the sense that \int_{-1}^{1}(1-x)^{\alpha}(1+x)^{\beta}P^{(\alpha,\beta)}_{i}(x)P^{(\alpha,\beta)}_{j}(x)\,\mbox{d}x=\delta_{ij}h_{i}, where \delta_{ij} denotes the Kronecker delta , h_{i}>0 , and \Pi_{\ell} is the set of polynomials of degree \leq\ell ( \Pi_{-1}:=\emptyset ). We use the standard normalization P_{k}^{(\alpha,\beta)}(1)=\binom{k+\alpha}{k}\qquad(k=0,1,\ldots) which uniquely defines the Jacobi polynomials. In this paper, we focus on the case \alpha=\beta (which corresponds to the so-called Gegenbauer polynomials ). Thus, for simplicity, we set P^{(\alpha)}_{k}(x):=P^{(\alpha,\alpha)}_{k}(x)\qquad(k=0,1,\ldots;\,\alpha>-1). (2.1) The polynomials P^{(\alpha)}_{k} have the following explicit representation: \displaystyle P^{(\alpha)}_{k}(x)=\frac{(\alpha+1)_{k}}{k!}\,{}_{2}F_{1}\!\left(\begin{array}[]{cc}{\displaystyle{-k,\,k+2\alpha+1}}\\[1.07639pt] {\displaystyle{\alpha+1}}\end{array}\bigg|\,{\displaystyle{\frac{1-x}{2}}}\right)\qquad(k=0,1,\ldots), (2.2) where {}_{p}F_{q} is the generalized hypergeometric function , and (a)_{i} denotes the Pochhammer symbol (see, e.g., [ 3 ] , [ 6 ] ). They fulfill a recurrence relation, namely \displaystyle P_{k}^{(\alpha)}(x)=x\,\xi^{(\alpha)}_{1}(k)P_{k-1}^{(\alpha)}(x)-\xi^{(\alpha)}_{2}(k)P_{k-2}^{(\alpha)}(x)\qquad(k=2,3,\ldots), (2.3) where \xi^{(\alpha)}_{1}(k):=\frac{(k+\alpha)(2k+2\alpha-1)}{k(k+2\alpha)}\quad(k\geq 1),\qquad\xi^{(\alpha)}_{2}(k):=\frac{(k+\alpha-1)_{2}}{k(k+2\alpha)}\quad(k\geq 2), and P_{0}^{(\alpha)}(x)=1 , P_{1}^{(\alpha)}(x)=\xi^{(\alpha)}_{1}(1)\,x=(\alpha+1)x . Hence, for given x\in\mathbb{R} , m\in\mathbb{N} and \alpha>-1 , P^{(\alpha)}_{m}(x) can be evaluated in O(m) time. For k\in\mathbb{N} , we have the following symmetry: P_{k}^{(\alpha)}(x)=(-1)^{k}P_{k}^{(\alpha)}(-x). (2.4) The i th derivative of P_{k}^{(\alpha)} is also a symmetric Jacobi polynomial, i.e., \frac{\mbox{d}^{i}}{\mbox{d}x^{i}}P_{k}^{(\alpha)}(x)=\frac{(k+2\alpha+1)_{i}}{2^{i}}P_{k-i}^{(\alpha+i)}(x), (2.5) where k,i\in\mathbb{N} and we adopt the convention—used throughout the sequel—that P_{\ell}^{(\alpha)}\equiv 0 for \ell=-1,-2,\ldots . Let us consider the polynomial u_{m}\in\Pi_{m} (m\in\mathbb{N}) given in the symmetric Jacobi form , u_{m}(x)=\sum_{k=0}^{m}v_{k}P_{k}^{(\alpha)}(x), where the coefficients v_{0},v_{1},\ldots,v_{m}\in\mathbb{R} are known. Recall that, for a given x\in\mathbb{R} , the value u_{m}(x) can be computed in O(m) time using the famous Clenshaw algorithm (see, e.g, [ 2 ] ): 1. Set B_{m+1}=B_{m+2}:=0 . 2. For k=m,m-1,\ldots,0 , set B_{k}:=v_{k}+x\,\xi^{(\alpha)}_{1}(k+1)B_{k+1}-\xi^{(\alpha)}_{2}(k+2)B_{k+2}. Then u_{m}(x)=B_{0} . Note that the Clenshaw algorithm follows from the recurrence relation ( 2.3 ). 2.1 Legendre polynomials We write P_{k}(x):=P_{k}^{(0)}(x) for k=0,1,\ldots . Clearly, the polynomials P_{k} are the well-known Legendre polynomials . We will use the following classical Christoffel–Darboux formula for Legendre polynomials: \displaystyle\sum_{i=0}^{k}(2i+1)P_{i}(x)P_{i}(y)=(k+1)\frac{P_{k}(y)P_{k+1}(x)-P_{k}(x)P_{k+1}(y)}{x-y}, (2.6) where x\neq y , and k\in\mathbb{N} . It is also true that the indefinite integral of the polynomial P_{k} is given by \int P_{k}(x)\,\mbox{d}x=\frac{1}{2k+1}\left(P_{k+1}(x)-P_{k-1}(x)\right)+\mbox{const.}, (2.7) where k\geq 0 . Furthermore, it can be checked that \int P_{k}(x)\,\mbox{d}x=\frac{1}{k(k+1)}(x^{2}-1)\frac{\mbox{d}}{\mbox{d}x}P_{k}(x)+\mbox{const.}\\ (2.8) for k\geq 1 . Assumption 2.1 . From now on, let n\in\mathbb{N} be fixed. Let \tau_{i}\equiv\tau^{(n)}_{i} (i=1,2,\ldots,n;\ n>0) , -1<\tau_{1}<\tau_{2}<\cdots<\tau_{n}<1, (2.9) be the zeros of the n th Legendre polynomial. In this paper, we assume that the zeros \tau^{(n)}_{i} (i=1,2,\ldots,n) are known with high numerical accuracy, since they can be precomputed using, for example, the results presented in [ 4 ] , [ 5 ] . 3 Gauss-Legendre polynomials and curves The GL polynomials and the GL curves were recently introduced in [ 7 ] . We now recall their definitions, as well as some of their main properties proved in that paper. The GL polynomials F^{n}_{i}\in\Pi_{n}\setminus\Pi_{n-1} (i=0,1,\ldots,n) are given by F^{n}_{i}(t):=G^{n}_{i}(t)-G^{n}_{i+1}(t), (3.1) where G^{n}_{0}(t)=-G^{n}_{n+1}(t)\equiv\frac{1}{2} , and G^{n}_{i}(t):=\frac{nP_{n-1}(\tau_{i})}{2}\int_{-1}^{t}\frac{P_{n}(x)}{x-\tau_{i}}\,\mbox{d}x-\frac{1}{2}, (3.2) for i=1,2,\ldots,n . Polynomials F^{n}_{0},F^{n}_{1},\ldots,F^{n}_{n} form a basis of \Pi_{n} . They also give the partition of unity , i.e., \sum_{i=0}^{n}F^{n}_{i}(t)\equiv 1\qquad(t\in\mathbb{R}). We have F^{n}_{i}(-1)=\delta_{0i},\qquad F^{n}_{i}(1)=\delta_{ni}\qquad(i=0,1,\ldots,n). (3.3) Moreover, the following symmetries hold: F^{n}_{i}(-t)=-F^{n}_{n-i}(t)\quad(0\leq i\leq n), (3.4) because G^{n}_{i}(-t)=-G^{n}_{n-i+1}(t) for 0\leq i\leq n+1 . The GL curve \mbox{{P}}_{n}:[-1,1]\to\mathbb{E}^{d} (d\geq 1) of degree n is a parametric polynomial curve of the form \mbox{{P}}_{n}(t):=\sum_{i=0}^{n}\mbox{{W}}_{i}F^{n}_{i}(t), (3.5) where \mbox{{W}}_{0},\mbox{{W}}_{1},\ldots,\mbox{{W}}_{n}\in\mathbb{E}^{d} are the so-called control points . Note that \mbox{{P}}_{n}(-1)=\mbox{{W}}_{0} , \mbox{{P}}_{n}(1)=\mbox{{W}}_{n} (cf. ( 3.3 )). Although the GL curve does not lie in the convex hull of its control points, its graph closely follows its control polygon. This property has, in recent years, contributed to the growing popularity of these curves. 4 New representations for GL polynomials As mentioned in § 1 , the problem of evaluating GL curves was not considered in [ 7 ] . The purpose of this article is therefore to propose fast and numerically stable methods for computing points on a GL curve ( 3.5 ). In view of Eq. ( 3.1 ), the main problem is to efficiently evaluate G^{n}_{i}(t) for a given t\in[-1,1] and for all i=1,2,\ldots,n (cf. ( 3.2 )). To this end, we study the representations of polynomials G^{n}_{i} in (i) shifted power basis, and (ii) in symmetric Jacobi basis. 4.1 Shifted power basis Using ( 2.4 ) and ( 2.2 ), we obtain P_{n}(x)=\sum_{k=0}^{n}a_{k}(x+1)^{k}, (4.1) where a_{k}:=\frac{(-1)^{n-k}}{2^{k}}\binom{n}{k}\binom{n+k}{k}\qquad(0\leq k\leq n). Observe that 2(k+1)^{2}a_{k+1}+(n-k)(n+k+1)a_{k}=0, (4.2) where k=n-1,n-2,\ldots,0 , and a_{n}=\frac{1}{2^{n}}\binom{2n}{n}. Lemma 4.1 . Let the coefficients b^{(i)}_{k} (k=0,1,\ldots,n-1;\,1\leq i\leq n) be such that \frac{P_{n}(x)}{x-\tau_{i}}=\sum_{k=0}^{n-1}b^{(i)}_{k}(x+1)^{k} (4.3) (cf. ( 3.2 )). The following non-homogeneous first-order recurrence relation holds: b^{(i)}_{k-1}-(\tau_{i}+1)b^{(i)}_{k}=a_{k}\qquad(k=n,n-1,\ldots,1), (4.4) where b^{(i)}_{n}:=0 . In addition, the coefficients b^{(i)}_{k} satisfy the second-order homogeneous recurrence relation of the form (n-k)(n+k+1)b^{(i)}_{k-1}+(2(k+1)^{2}-(\tau_{i}+1)(n-k)(n+k+1))b^{(i)}_{k}-2(\tau_{i}+1)(k+1)^{2}b^{(i)}_{k+1}=0, (4.5) where k=n-1,n-2,\ldots,1 , b^{(i)}_{n-1}=a_{n} , and b^{(i)}_{n}:=0 . Proof. We have \displaystyle P_{n}(x) \displaystyle= \displaystyle(x-\tau_{i})\sum_{k=0}^{n-1}b^{(i)}_{k}(x+1)^{k}=(x+1-(\tau_{i}+1))\sum_{k=0}^{n-1}b^{(i)}_{k}(x+1)^{k} \displaystyle= \displaystyle\sum_{k=0}^{n-1}b^{(i)}_{k}(x+1)^{k+1}-(\tau_{i}+1)\sum_{k=0}^{n-1}b^{(i)}_{k}(x+1)^{k} \displaystyle= \displaystyle\sum_{k=0}^{n}\left(b^{(i)}_{k-1}-(\tau_{i}+1)b^{(i)}_{k}\right)(x+1)^{k}, where b^{(i)}_{-1}=b^{(i)}_{n}:=0 . It follows that the recurrence ( 4.4 ) holds. Combining ( 4.4 ) with ( 4.2 ) yields the recurrence ( 4.5 ). ∎ Remark 4.2 . Solving the recurrence ( 4.4 ) gives an explicit expression for the coefficients b^{(i)}_{k} , b^{(i)}_{k}=a_{k+1}\,{}_{3}F_{2}\!\left(\begin{array}[]{cc}{\displaystyle{k-n+1,\,n+k+2,\,1}}\\[1.07639pt] {\displaystyle{k+2,\,k+2}}\end{array}\bigg|\,{\displaystyle{\frac{\tau_{i}+1}{2}}}\right) (cf. ( 4.1 )), where k=0,1,\ldots,n-1 . Now, it is easy to integrate the expansion ( 4.3 ) over x\in[-1,t] (-1\leq t\leq 1) and obtain a representation of the polynomials F^{n}_{i} (i=0,1,\ldots,n) in the shifted power basis. Summarizing, the following statements are true. Theorem 4.3 . The GL polynomial F^{n}_{i} (cf. ( 3.1 )) has the following representation in the shifted power basis: F^{n}_{i}(t)=\sum_{k=1}^{n}c^{(i)}_{k}(t+1)^{k}, where i=1,\ldots,n-1 , and c^{(i)}_{k}:=\frac{n}{2k}\left(P_{n-1}(\tau_{i})b^{(i)}_{k-1}-P_{n-1}(\tau_{i+1})b^{(i+1)}_{k-1}\right)\qquad(1\leq k\leq n). (4.6) We also have \displaystyle F^{n}_{0}(t)=1-\frac{1}{2}nP_{n-1}(\tau_{1})\sum_{k=1}^{n}\frac{1}{k}b^{(1)}_{k-1}(t+1)^{k}, \displaystyle F^{n}_{n}(t)=\frac{1}{2}nP_{n-1}(\tau_{n})\sum_{k=1}^{n}\frac{1}{k}b^{(n)}_{k-1}(t+1)^{k}. Hence, for fixed 0\leq i\leq n , F^{n}_{i}(t) (t\in\mathbb{R}) can be evaluated using Horner’s scheme (see, e.g., [ 2 ] ) in O(n) time (cf. recurrences ( 2.3 ), ( 4.2 ) and Lemma 4.1 ). Corollary 4.4 . For a given t\in(-1,1) (cf. ( 3.3 )), all the values F^{n}_{0}(t),F^{n}_{1}(t),\ldots,F^{n}_{n}(t) can be evaluated in O(n^{2}) time using Horner’s schemes for representations given in Theorem 4.3 . Note that the cost of the computations can be reduced using the symmetries ( 2.4 ), ( 3.4 ). This is discussed in Section 5.1 . Thus, using the approach described in this paragraph, a point on the GL curve ( 3.5 ) in \mathbb{E}^{d} can be computed component-wise with a computational complexity of O(n^{2}+dn) . 4.2 Symmetric Jacobi basis In this paragraph, we show that, using the Christoffel–Darboux identity ( 2.6 ) and other results presented in Section 2 , one can derive simple expansions of the polynomials G^{n}_{i} (i=1,\ldots,n) closely related to the symmetric Jacobi bases. Note that the coefficients in those representations are given in terms of the values of Legendre polynomials at the zeros \tau_{1},\tau_{2},\ldots,\tau_{n} of P_{n} . Let us define R_{k}(t):=P_{k+1}(t)-P_{k-1}(t)\qquad(k=0,1,\ldots). (4.7) Lemma 4.5 . For i=1,2,\ldots,n , the following identities are true: G^{n}_{i}(t)=-\frac{1}{2}\sum_{k=0}^{n-1}R_{k}(\tau_{i})P_{k}(t)+\frac{1}{2}P_{n-1}(\tau_{i})P_{n}(t). (4.8) G^{n}_{i}(t)=\frac{t}{2}+\frac{t^{2}-1}{2}\sum_{k=1}^{n-1}\frac{2k+1}{2k}P_{k}(\tau_{i})P^{(1)}_{k-1}(t). (4.9) Proof. From the recurrence relation ( 2.3 ) for k:=n+1 , \alpha:=0 , and x:=\tau_{i} (cf. ( 2.9 )), it follows that (n+1)P_{n+1}(\tau_{i})=-nP_{n-1}(\tau_{i}), (4.10) because P_{n}(\tau_{i})=0 . While from the Christoffel–Darboux formula ( 2.6 ) with k:=n and y:=\tau_{i} , we have \displaystyle\sum_{k=0}^{n}(2k+1)P_{k}(\tau_{i})P_{k}(x)=-(n+1)P_{n+1}(\tau_{i})\frac{P_{n}(x)}{x-\tau_{i}}=nP_{n-1}(\tau_{i})\frac{P_{n}(x)}{x-\tau_{i}}, (4.11) where we used ( 4.10 ). Here i=1,2,\ldots,n . Integrating the right-hand side of ( 4.11 ) over x\in[-1,t] with t\in[-1,1] and using ( 2.7 ), we get ( 4.8 ), because P_{k}(-1)=(-1)^{k} for k\in\mathbb{N} (cf. ( 4.1 )). Applying ( 2.5 ) for \alpha:=0 , i:=1 to ( 2.8 ), we obtain \int P_{k}(x)\,\mbox{d}x=\frac{1}{2k}(x^{2}-1)P^{(1)}_{k-1}(x)+\mbox{const.}\qquad(k\geq 1) (cf. ( 2.1 )). Integrating as above and using the latter, we derive the identity ( 4.9 ). ∎ We are now ready to formulate the main results of this paragraph. Theorem 4.6 . The GL polynomial F^{n}_{i} (cf. ( 3.1 )) has the following representation in the Legendre basis: F^{n}_{i}(t)=\frac{1}{2}\left(P_{n-1}(\tau_{i})-P_{n-1}(\tau_{i+1})\right)P_{n}(t)+\frac{1}{2}\sum_{k=0}^{n-1}\left(R_{k}(\tau_{i+1})-R_{k}(\tau_{i})\right)P_{k}(t), where i=1,\ldots,n-1 . We also have \displaystyle F^{n}_{0}(t)=\frac{1}{2}-\frac{1}{2}P_{n-1}(\tau_{1})P_{n}(t)+\frac{1}{2}\sum_{k=0}^{n-1}R_{k}(\tau_{1})P_{k}(t), \displaystyle F^{n}_{n}(t)=\frac{1}{2}+\frac{1}{2}P_{n-1}(\tau_{n})P_{n}(t)-\frac{1}{2}\sum_{k=0}^{n-1}R_{k}(\tau_{n})P_{k}(t). Theorem 4.7 . The GL polynomial F^{n}_{i} can be written as: F^{n}_{i}(t)=\frac{1}{2}(t^{2}-1)\left(\sum_{k=1}^{n-1}\frac{2k+1}{2k}(P_{k}(\tau_{i})-P_{k}(\tau_{i+1}))P^{(1)}_{k-1}(t)\right) (cf. ( 2.1 )), where i=1,\ldots,n-1 . It is also true that \displaystyle F^{n}_{0}(t)=1-\frac{1}{2}(t+1)\left(1+(t-1)\sum_{k=1}^{n-1}\frac{2k+1}{2k}P_{k}(\tau_{1})P^{(1)}_{k-1}(t)\right), \displaystyle F^{n}_{n}(t)=\frac{1}{2}(t+1)\left(1+(t-1)\sum_{k=1}^{n-1}\frac{2k+1}{2k}P_{k}(\tau_{n})P^{(1)}_{k-1}(t)\right). Observe that the expansions given in Theorem 4.7 immediately imply ( 3.3 ). These representations are also better suited for practical applications than those in the Legendre basis (cf. Theorem 4.6 and Eq. ( 4.7 )). However, by using both results, the recurrence relation ( 2.3 ) and the Clenshaw algorithm (see § 2 , p. 2 ), the value F^{n}_{i}(t) for a given t\in\mathbb{R} can be computed with O(n) computational complexity. Corollary 4.8 . Let t\in(-1,1) (cf. ( 3.3 )). All the values F^{n}_{0}(t),F^{n}_{1}(t),\ldots,F^{n}_{n}(t) can be evaluated in O(n^{2}) time using the Clenshaw algorithm for the representations given in Theorems 4.6 or 4.7 . As noted (cf. Corollary 4.4 ), the computational cost can be decreased using the symmetries ( 2.4 ), ( 3.4 ). This is discussed in Section 5.2 , where we make use of Theorem 4.7 . In summary, using the methods proposed in this paragraph, one can evaluate a point on the GL curve ( 3.5 ) in \mathbb{E}^{d} component-wise with O(n^{2}+dn) computational complexity. 4.3 Derivatives In [ 7 , Theorem 16] a complicated general formula for the m th derivative of a GL polynomial F^{n}_{i} was derived, where the derivative is expressed in terms of elementary symmetric polynomials . It is now clear that, using the representations of GL polynomials from § 4.1 and § 4.2 , we can find simple expressions for their m th derivatives. For example, if 1\leq i\leq n-1 and m>0 , we have \frac{\mbox{d}^{m}}{\mbox{d}t^{m}}F^{n}_{i}(t)=\sum_{k=m}^{n}(k-m+1)_{m}c^{(i)}_{k}(t+1)^{k-m} (4.12) (cf. Theorem 4.3 ) and, in particular, \frac{\mbox{d}^{m}}{\mbox{d}t^{m}}F^{n}_{i}(-1)=(-1)^{m+1}\frac{\mbox{d}^{m}}{\mbox{d}t^{m}}F^{n}_{n-i}(1)=m!c^{(i)}_{m}\qquad(i=1,2,\ldots,n-1). On the other hand, using ( 2.5 ) for \alpha:=0 yields the following formula: \frac{\mbox{d}^{m}}{\mbox{d}t^{m}}F^{n}_{i}(t)=\frac{(n+1)_{m}}{2^{m+1}}\left(P_{n-1}(\tau_{i})-P_{n-1}(\tau_{i+1})\right)P_{n-m}^{(m)}(t)+\frac{1}{2^{m+1}}\sum_{k=m}^{n-1}(k+1)_{m}d^{(i)}_{k}P_{k-m}^{(m)}(t), (4.13) where d^{(i)}_{k}:=R_{k}(\tau_{i+1})-R_{k}(\tau_{i}) (see Theorem 4.6 and ( 4.7 )). Note that the expression ( 4.12 ) can be evaluated in O(n-m) time using the Horner’s scheme. Similarly, for a given t\in\mathbb{R} , Eq. ( 4.13 ) can be computed with the same computational complexity by applying the recurrence ( 2.3 ) and the Clenshaw algorithm (cf. § 2 , p. 2 ). Certainly, the derivatives of F^{n}_{0} and F^{n}_{n} can be obtained in a similar way. 5 Evaluation We now turn to the problem of evaluating a GL curve \mbox{{P}}_{n} of degree n in \mathbb{E}^{d} (see ( 3.5 )). More precisely, based on the results presented in § 4 , we propose two methods for computing F^{n}_{0}(t),F^{n}_{1}(t),\ldots,F^{n}_{n}(t) for a fixed t\in\mathbb{(}-1,1) (cf. ( 3.3 )), which run with O(n^{2}) computational complexity. Once all these values are known, one can determine a point \mbox{{P}}_{n}(t) component-wise in O(nd) time. This results in a total computational complexity of O(n^{2}+dn) (see Corollaries 4.4 , 4.8 ). Moreover, we present a sketch of the algorithms for the evaluation of M points on the curve \mbox{{P}}_{n} , which work in O(Mdn+dn^{2}) time. First of all, let us note that there is a possibility of reducing the computational cost by using the symmetries ( 3.4 ). Indeed, it is enough to consider the problem of evaluating F^{n}_{0},F^{n}_{1},\ldots,F^{n}_{\left\lfloor{n/2}\right\rfloor}, because we have \mbox{{P}}_{n}(t)=\sum_{i=0}^{\left\lfloor{n/2}\right\rfloor}\mbox{{W}}_{i}F^{n}_{i}(t)-\sum_{i=\left\lfloor{n/2}\right\rfloor+1}^{n}\mbox{{W}}_{i}F^{n}_{n-i}(-t). (5.1) 5.1 First approach: shifted power basis Let us use the results from § 4.1 . First, we need to compute P_{n-1}(\tau_{i})\qquad(i=1,2,\ldots,\left\lceil{n/2}\right\rceil) (cf. Assumption 2.1 ). This can be accomplished by the recurrence relation ( 2.3 ) with \alpha:=0 in O(\frac{1}{2}n^{2}) time. It is also worth making use of the following simple observation. For odd n=2m+1 , one of the zeros of P_{n} is equal to 0 . Then n-1 is even and P_{n-1}(0)=\frac{(-1)^{m}}{4^{m}}\binom{2m}{m}. In the second step, we determine the coefficients b^{(i)}_{k} (see ( 4.3 )) for all i=1,2,\ldots,\left\lceil{n/2}\right\rceil (cf. ( 4.6 )) and all k=0,1,\ldots,n-1 . It should be done with the help of the recurrence relations ( 4.4 ) and ( 4.2 ). Finally, for a given t\in(-1,1) , we obtain the values F^{n}_{0}(\pm t),F^{n}_{1}(\pm t),\ldots,F^{n}_{\left\lfloor{n/2}\right\rfloor}(\pm t) (5.2) by using the Horner’s schemes for expansions given in Theorem 4.3 and thus we also find component-wise the point \mbox{{P}}_{n}(t) (cf. ( 5.1 )). Note that this approach has O(n^{2}+dn) computational complexity when computing a single point on an n th-degree GL curve in \mathbb{E}^{d} . 5.2 Second approach: symmetric Jacobi basis Now, we present another technique for evaluating GL curves, which uses the representations from Theorem 4.7 . Note that the same can be done for the representations from Theorem 4.6 . To this end, in the first step, we have to find the following values of the Legendre polynomials: P_{k}(\tau_{i})\qquad\mbox{for all $k=1,2,\ldots,n-1$ and $i=1,2,\ldots,\left\lceil{n/2}\right\rceil$}. Again, this can be done using the recurrence relation ( 2.3 ) with \alpha:=0 in O(\frac{1}{2}n^{2}) computational complexity. If n is odd, one of the zeros of P_{n} is equal to 0 . In this case, we have P_{k}(0)=0\quad\mbox{for odd $k$},\qquad P_{k}(0)=\frac{(-1)^{k/2}}{2^{k}}\binom{k}{k/2}\quad\mbox{for even $k$}. Next, for a fixed -1