Parametric Curves and Applications in CAGD: Introduction and some Special Issues

T. Recio^{∗}  J.R. Sendra & J. Sendra^{†}
Dpto. de Matemáticas  Dpto. de Matemáticas
Universidad de Cantabria  Universidad de Alcalá
Santander 39071 (Spain)  Madrid 28871 (Spain)
recio@matsun1.unican.es  mtsendra@alcala.es

In this paper we briefly introduce the notion and main problems related to parametric curves, and we focus on two issues specially interesting in applications: the problem of computing real reparametrization of real parametric curves, and the rationality analysis and parametrization of offset curves of parametric curves.

Let IK be a field of characteristic zero and K its algebraic clousure. An algebraic variety V in the affine n-space K^{n} implicitely defined by the system of polynomial equations

V = {f_{1}(x_{1}, …, x_{n}) = 0, …, f_{r}(x_{1}, …, x_{n}) = 0}

f_{1}, …, f_{r} ∈ IK[x_{1}, …, x_{n}], is called parametric if there exist rational functions p_{1}, …, p_{n} ∈ K(t_{1}, …, t_{m}) such that f_{i}(p_{1}(t_{1}, …, t_{m}), …, p_{n}(t_{1}, …, t_{m})) is identically zero for i = 1, …, r. Then, we say that (p_{1}, …, p_{n}) is a rational parametrization of V. Every parametrization of V can also be seen as a map P from K^{m} to K^{n} such that for almost every parameter value t̄ = (t_{1}, …, t_{m}) ∈ K^{m} (i.e. for all but a finite number of exceptions) P(t̄) = (p_{1}(t̄), …, p_{n}(t̄)) is a point of the variety V.

Here we deal with parametric curves; more particularly with parametric plane curves. Geometric questions related to parametric curves in higher dimension spaces can be studied considering birationally equivalent plane curves. Thus, we are dealing with varieties C in K^{2} that can be represented implicitaly by a polynomial f(x, y) ∈ IK[x, y]

C = {(a, b) ∈ K^{2} / f(a, b) = 0}

or parametricaly as P(t) = (p_{1}(t), p_{2}(t)), where p_{1}, p_{2} ∈ K(t).

If one starts from the implicit representation of the variety the question of computing rational parametric representations arises (parametrization problem), and the preliminary subproblem of deciding whether the curve can be parametrized has also to be considered (rationality problem). Parametric curves, or rational curves, are exactly the irreducible curves of genus zero. The genus is a birational invariant of the curve, that measures the deficient between the maximum allowable limit of singularities and the number of singularities of the curve, counted properly with multiplicities (if the curve has degree d then \frac{(d−1)(d−2)}{2} bounds the number of double points). Thus, parametric curves are the irreducible curves with the maximum allowable number of singularities; for instance: conics, cubics with one double point, . . .. Hence, the rationality of the curve can be decided analyzing the multiplicity of the singularitites. Recently, several algorithms for computing the genus and rational parametrizations have been proposed [1],[13],[17],[21],[22].

∗Partially supported by CICyT PB 92/0498/C02/01 (Geometría Real y Algoritmos), Esprit/Bra 6846 (Posso), and TIC-1026-CE

†Partially supported by Univ. Alcalá Proy. 030/95

If one starts from the parametric representation of the variety, the natural question of determining the defining polynomial, or defining system of polynomials in the higher dimension case, appears (implicitization problem). Implicitization procedures can be found for instance in [6],[11]. Also, many authors have addressed the problem of computing good parametrizations; where good affects to the degree of the rational functions in the parametrization, to the algebraic field extension where the parametrization is expressed, and to the coefficient lenght in the parametrization. Proper parametrizations (i.e. parametrizations with optimal degree) are reached in [1],[13],[17],[21], [22]. Reparametrization methods for improperly parametrized curves, and algorithmic criteria for the existence of polynomial parametrizations are also available, for instance, in [2],[6],[11]. In [22] a procedure for determining parametrizations expressed over the smallest possible field extension of the ground field is presented. Similar theoretical results can be found in [17]. Nevertheless, purely arithmetic questions (for instance, the determination of upper bounds of the lenght of the coefficients of the rational functions involved in the parametrization) are still open questions.

In addition, complexity analysis of some of these problems have been presented in [14],[23], and computer packages for dealing with algebraic curves and rational function fields are developed in [4],[10].

Parametric curves play an important role in the field of Computer Aided Geometric Design. They arise in practical applications as computer graphics, geometric modeling or manipulation of offset varieties. The natural field of applications of rational curves is Computer Aided Design. Indeed, real varietes are the most common ones in Geometric Design. However, since Algebraic Geometry is mainly developed over algebraically closed fields, the majority of the previous algorithms are checked only over the complex numbers. Thus, the usually forgotten reality issues are not treated. Special exceptions are: [3],[5],[9] where the existence of real parametrizations is analyzed, [16] where a real reparametrization algorithm is presented, and [22] where a parametrization algorithm, that computes real parametrizations when they exist, is given.

An interesting problem to mention is the algebraic manipulation of offset curves. Offset curves of a given curve, or more formerly parallel curves, are defined as the envelopes of systems of circles with centres on the original curve and fixed radious. They arise in practical applications as tolerance analysis, geometric control, robot path-planning and numerical-control machining problems. In [7],[8] the principal geometric and topological properties of offset curves are stated, and an algorithmic approach, based on resultants, to compute the implicit equation of an offset plane curve is provided. Similarly, in [12] it is shown how to use Computer Algebra techniques as Gröbner Basis (or any other algebraic equation solver as Characteristic Sets) to determine implicit equations of the offset of rational surfaces. One of the main problems in offset curves manipulation is that the rationality of the original curve is not preserved (in general) when the offset curve is considered. Pottman gives explicit formulas to produce rational plane curves and surfaces whose offsets have rational components [15]. Nevertheless, it is not algorithmically clear how to deduce if a given curve has an offset with rational components, and how to compute a rational offset parametrization, if they exist. In [19],[20] a complete rationality analysis of the offset curves is presented, and symbolic algorithms to parametrize the rational components of the offset curves to parametric curves are derived.

In the sequel, we present the main ideas of the real reparametrization algorithm developed in [16], and we briefly summarize the rationality analysis and parametrization algorithm for offset curves given in [19],[20].

Real Reparametrizations of Curves

Let C be a plane curve defined by a real polynomial f ∈ IR[x, y], with f irreducible over the complexes. Let us assume that C is rational, and let P(t) be a rational proper complex parametrization of C. Then, we study the existence and computation –by reparametrizations of P(t)– of real parametrizations of C. For this purpose, we associate with C an additional curve that provides the complex parameter values that generates –via P– the real points on C.

More precisely, let t̄ = t_{1} + i t_{2}, t_{1}, t_{2} ∈ IR, denote a generic complex number. Then the parametrization P(t) can be written in the form:

P(t̃) = (\frac{h_{1}(t_{1}, t_{2}) + i f_{1}(t_{1}, t_{2})}{m_{1}(t_{1}, t_{2})}, \frac{h_{2}(t_{1}, t_{2}) + i f_{2}(t_{1}, t_{2})}{m_{2}(t_{1}, t_{2})})

where m_{1}, m_{2}, h_{1}, h_{2}, f_{1}, f_{2} ∈ IR[x, y]. Now, if C is parametrizable over the reals, there exist infinitely many points (t_{1}, t_{2}) ∈ IR^{2} such that P(t_{1} + i t_{2}) is a real point on C. Therefore the curves F_{1}, F_{2}, defined respectively by f_{1}(t_{1}, t_{2}) and f_{2}(t_{1}, t_{2}), have infinitely many common points, and hence, they have common components. Let C̃ be the curve defined by the common components of F_{1} and F_{2}. Observe that C̃ has real points, and that the mapping

\begin{matrix}φ : C̃ & ⟶ & C \\ (a, b) & ⟶ & P(a + i b) \end{matrix}

is a one-to-one mapping of the set of almost all real points of C̃ (i.e. all but a finite number of exceptions) onto the set of almost all real points of C.

The following theorem states the algebraic properties of C̃ and the mapping φ that allow us to construct the real reparametrization algorithm. Theorem 1.

(1) C̃ has exactly one real component. Furthermore, it is either a real circle or a real line. In the sequel, although it may be a line, we will refer to the real component C^{⋆} of C̃ as the associated real conic with C.

(2) C is parametrizable over IR if and only if C̃ has a real circle or a real line as a component.

(3) If C is parametrizable over IR then for every real parametrization (\frac{m_{1}(t)}{m_{2}(t)}, \frac{m_{3}(t)}{m_{4}(t)}) of C^{⋆} it holds that P(\frac{m_{1}}{m_{2}} + i \frac{m_{3}}{m_{4}} ) is a proper real parametrization of C.

Thus, since C^{∗} is rational (it is a circle or a line) and it is easy to check whether it has real points. The previous ideas can be summarized in an algorithm. Given a proper complex parametrization P(t) of an affine plane curve C, the algorithm decides whether C can be parametrized over the reals, and if so a proper real parametrization is computed. \underline{Algorithm}

1. Take t̄= t_{1} + i t_{2} and compute P(t̄) = (\frac{h_{1}(t_{1},t_{2})+i f_{1}(t_{1},t_{2})}{m_{1}(t_{1},t_{2})}, \frac{h_{2}(t_{1},t_{2})+i f_{2}(t_{1},t_{2})}{m_{2}(t_{1},t_{2})})

where m_{1}, m_{2}, h_{1}, h_{2}, f_{1}, f_{2} ∈ IR[x, y].

2. Find the real factors of g̃(t_{1}, t_{2}) = gcd(f_{1}, f_{2}).

3. If g̃ has neither a real circle nor a line as a real factor, then Return that C is not real.

4. Take g^{⋆}(t_{1}, t_{2}) as the real circle factor or the real line factor of g̃(t_{1}, t_{2}).

5. Obtain a real proper parametrization (\frac{m_{1}(t)}{m_{2}(t)}, \frac{m_{3}(t)}{m_{4}(t)}) of g^{⋆}(t_{1}, t_{2}).

7. Return P(\frac{m_{1}}{m_{2}} + i \frac{m_{3}}{m_{4}} ).

Parametrization of Offset Curves

Let C be a parametric curve over K given by P(t) = (p_{1}(t), p_{2}(t)), p_{1}, p_{2} ∈ K(t) (we exclude the trivial case where C is a line). Then, the offset curve to C at distance d is the set of all points of the affine plane over K given by the formula

P(t) ± \frac{d}{m(t)} N (t),

where N (t) = (−p′_{2}(t), p′_{1}(t)) is the normal vector, and m(t) = \sqrt{p′_{1}(t)^{2} + p′_{2}(t)^{2}} is its length. In the sequel, we denote by O_{d} the offset curve to C at distance d. Note that O_{d} is the envelope of the system of circles with centre on C and radious d.

One of the main problems in offset curves manipulation is that the rationality of the original curve is not preserved (in general) when the offset curve is considered. In the following we give a characterization of those parametric curves with parametric offsets, as well as an algorithm for parametrizing parametric offsets.

For this purpose, we introduce the following notion: let P(t) = (p_{1}(t), p_{2}(t)) be a proper parametrization of C. Then, the curve of reparametrization of O_{d} associated with P is defined as the plane curve given by the primitive part –w.r.t y– of the numerator of 2p′_{2}(x)y + p′_{1}(x)(y^{2} − 1), and it is denoted as G_{P}. Then one has the following characterizations: Theorem 2. The following statements are equivalent

(1) All the components of O_{d} are rational

(2) There exists φ ∈ K(t) of degree at most two, and a rational proper parametrization P(t) of C such that the normal vector of P(φ(t)) has rational length.

(3) There exists a proper parametrization P of C such that at least one component of G_{P} is rational. Furthermore, if (R_{1}, R_{2}) parametrizes the component of G_{P} then P(R_{1}(t)) has normal vector with rational length.

As a consequence of theorem 2 one may deduce that the rationality of the offset curves does not depened on the distance. That is, either all the components of O_{d} are rational at any nonzero distance, or both components have positive genus at any nonzero distance. Therefore, the geometric analysis of the offest can be done at a fixed distance. Indeed, one may be more precise and distinguishes the cases of rational offsets or offsets with two rational components. Theorem 3. The following statements are equivalent

(1) O_{d} is rational

(2) There exists a rational parametrization P of C such that G_{P} is rational.

(3) For every rational parametrization P of C the curve G_{P} is rational. Theorem 4. The following statements are equivalent:

(1) O_{d} has two rational components

(2) There exists a rational proper parametrization P of C such that G_{P} is reducible.

(3) For every rational proper parametrization P of C the curve G_{P} is reducible. We finish this paper with the algorithm that summarizes the previous ideas. Given a proper parametrization P(t) of an affine plane curve C, it decides whether the components of O_{d} are rational, and if so, rational parametrizations of all the components are computed. \underline{Algorithm}

1. N := (−p′_{2}, p′_{1}); If ||N || ∈ K(t) then return ≪ O_{d} has two rational components; P ± \frac{d}{||N ||} N parametrizes the components of O_{d} ≫

2. Compute the genus g of the curve G_{P} defined by 2p′_{2}(x)y + p′_{1}(x)(y^{2} − 1).

3. If g ≠ 0 then return ≪ no component of O_{d} is rational ≫ else 3.1. Determine a rational parametrization R = (R_{1}, R_{2}) of G_{P}. 3.2. Return ≪ O_{d} is rational and Q = P(R_{1}) + \frac{2 d R_{2}}{n_{2}(R_{1})(R_{2}^{2}+1)} N (R_{1}) parametrizes O_{d} ≫.

References

[1] Abhyankar S.S, Bajaj C.L., (1988), Automatic parametrization of rational curves and surfaces III: Algebraic plane curves. Computer Aided Geometric Design 5, 390-321.

[2] Abhyankar S., (1990), Algebraic Geometry for scientists and engineers. Mathematical surveys and monographs, 35. A.M.S. 1990.

[3] Alonso C., Gutiérrez J., Recio T., Reconsidering algorithms for real parametric curves. To appear in J. AAECC.

[4] Alonso C., Gutiérrez J., Recio T., (1994), FRAC: A Maple package for computing in the rational function field K(X). MapleV: Mathematics and Its Applications, pp. 107-115. (Ed. R.J. Lopez) Birkhauser (1994).

[5] Bajaj C., Royappa A. V., (1992), Finite representations of real parametric curves and surfaces. Technical Report, CAPO Report CER-92-28. Purdue University, september 1992.

[6] Cox D., Little J., O’Shea D., (1992), Ideals, varieties and algorithms (An Introduction to Computational Algebraic Geometry and Commutative Algebra). Springer Verlag

[7] Farouki R. T., Neff C.A. (1990), Analytic properties of plane offset curves. Comput. Aided Geom. Design 7 83-99.

[8] Farouki R. T., Neff C.A. (1990), Algebraic properties of plane offset curves. Comput. Aided Geom. Design 7 100-127.

[9] Gutiérrez J., Recio T., (1992), Rational function decomposition and Groebner basis in the parametrization of a plane curve. LATIN 92. L.N.C.S. 583, Springer-Verlag. 1992, pp. 231-246.

[10] Gebauer R., Kalkbrener M., Wall B. and Winkler F.,(1991), CASA: A Computer Algebra Package for Constructive Algebraic Geometry. In S. M. Watt (ed.) Proc. ISSAC’91, 403-410, ACM Press.

[11] Hoffmann C., (1989) Geometric and Solid Modeling: An Introduction. Morgan Kaufmann, USA (1989).

[12] Hoffman C. (1990), Algebraic and Numerical Techniques for Offsets and Blends. W. Dahmen et al. (eds.), Computation of Curves and Surfaces, (Kluwer Ac. Publ.) 499-528.

[13] van Hoeij M. (1994), Computing parametrizations of rational algebraic curves. In J. von zur Gathen (ed.), Proc. ISSAC94 187-190, ACM Press.

[14] Mn̈uk M., Sendra J.R., Winkler F. (1993), On the Complexity of Parametrizing Curves. Techn. Rep. RISC 93-51, Research Inst. Symb. Comp., Univ. Linz.

[15] Pottman H., (1994), Rational curves and surfaces with rational offsets. Tech. Rep. Nr.1. Institut für Geometrie, Technische. Univ. Wien.

[16] Recio T., J.R. Sendra (1995) Real Reparametrizations of Real Curves. Technical Report. Dep. Matemáticas, Universidad de Cantabria.

[17] Schicho J., (1992) On the choice of pencils in the parametrization of curves. J. Symbolic Computation 14, 557-576.

[18] Sederberg, T.W. (1986), Improperly parametrized rational curves. Computer Aided Geometric Design 3, 67-75.

[19] Sendra J.R., Sendra J. (1995), On the Rationality of Offset Curves. Techn. Rep. RISC 95-02, Research Inst. Symb. Comp., Univ. Linz.

[20] Sendra J.R., Sendra J. (1995), Curvas Offset Racionales. Preprint.

[21] Sendra J.R., Winkler F. (1991), Symbolic Parametrization of Curves. J. Symbolic Computation 12/ 6, 607-631.

[22] Sendra J.R., Winkler F. (1994), Optimal Parametrization of Algebraic Curves. Techn. Rep. RISC 94-65, Research Inst. Symb. Comp., Univ. Linz.

[23] Teitelbaum J. (1989), On the Computational Complexity of the resolution of plane curve singularities. ISSAC-89 LNCS no. 358, pp. 285-292. Springer Verlag

[24] Walker R.J. (1950), Algebraic Curves. Princeton Unversity Press.