A Grobner Bases Approach to the Detection of Improperly Parameterized Rational Curve ()
1. Introduction
Rational curves (also called unicursal curves) play an important role in past and present computer development in such areas as geometric modeling and computer graphics.By definition, a rational curve is any curve that can be represented parameterically in the form
, 
, 
where
, 
, 
and
are polynomials [1,2].
Theoretically, given any curve either in the explicit, implicit or parametric form, it is important to know whether parameterization exists for the curve or not before attacking the problem of detecting improper parameterization. The above question is simple and can be answered by just checking for the genus of the curve. If the genus of a curve is zero, then it can be parameterized otherwise no parameterization exists for the curve [3-7]. Furthermore, it is only possible to use rational polynomial parametric equations to give an exact representation of a curve iff its genus is zero [8,9].
The concept of parameterization is very important in rational curves (our present interest) in particular and curves and surfaces in general; due to the fact that parametric representations are very easy to handle (implement) during computations [10,11].
A rational curve [12] is said to either be properly (also called faithful in the literature) or improperly parameterized depending on which definition for proper and improper parameterization is considered and, to our knowledge, two schools of taught exist. One of the schools defines a properly parameterized rational curve as one which upon reparameterization gives a one-to-one relationship between the initial curve and the reparameterized curve, otherwise it is improperly parameterized [2]. The other school defines proper parameterization in terms of the tracing index of the parameterization i.e. the number of times the parameterization traces the curve [4]. In this piece of work, the former definition is employed.
In 1986, an algorithm [2] which is capable of detecting improperly parameterize rational curves and how to reparameterize such curves, so as to attain proper parameterization was presented. This algorithm utilizes the notion of the Euclidean algorithm to compute the greatest common divisor (GCD) of two polynomials in one variable.
In this paper, we show that it is also possible to detect improper parameterization using the concept of Gröbner bases. We use a necessary and sufficient condition, i.e. the resultant must equal zero [13] to reveal the existence of a common Gröbner basis in a system of polynomials.
The remainder of this paper is organized as follows: Section 2 presents our algorithm for the detection of an improper parameterization. Section 3 reviews a numerical example [2]. Analysis of our algorithm is given in Section 4, and the last section concludes the work.
2. Algorithm for Detecting an Improperly Parameterized Rational Curve
In this section, we introduce our algorithm. First of all we would like to describe the definition and notation of some of the mostly used terms in this paper.
Definition 2.1: If a polynomial f in 
with coefficients in k is a linear combination of monomials, then the polynomial f can be written in the form
where the summation is taken over a finite number of n-tuples
, where 
are nonnegative integers. This set of polynomials in 
with coefficients in k is denoted as
.
Thus, polynomials in one, two and three variables lie in
, 
and
, respectively. Therefore, 
denotes a field in n-variables and a field with one variable 
is normally denoted by k.
Definition 2.2: An ideal is a subset 
which satisfies the following:
1)
2) If
, then
, and 3) If 
and
, then
.
Definition 2.3: Let 
be polynomials in 
and let the subset I be an ideal. Then I can be written in the form
Definition 2.4: Let 
denote a nonzero polynomial.
1) By letting
, 
and 
where 
for every j; then 
is called the least common multiple of 
and
, written in the form 
, where 
and 
are the leading monomials of u and v respectively and 
and 
are the multidegrees of u and v respectively.
2) The S-polynomial of u and v is the combination
where 
and 
are the leading terms of u and v respectively.
Definition 2.5: 
is defined as the remainder on division of 
by the ordered s-tuple .
Corollary 2.1: Suppose 
are polynomials both of positive degrees, then f and g are said to have a common Gröbner basis if and only if
where 
denotes the resultant of f and g with respect to x and 
denotes the determinant of the Sylvester matrix of f and g with respect to x ([10] p. 157, Proposition 8).
Corollary 2.2: Given a Gröbner basis 
of an ideal 
or
, if 
is any polynomial and 
,then the following statements are true
where 
is a constant for
, and 
([10] p. 76, Theorem 4).
Given a plane rational curve of the form
(1)
It is well known from Luroth’s theorem [14] that if Equation (1) is improperly parameterized i.e. does not give a one-to-one correspondence between the initial curve and the reparameterized curve, it is possible to reparameterize it to a properly parameterized rational curve of the form
(2)
where
(3)
If a nonsingular point 
exists, then
(4)
for some
.
We let 
and 
where p is a parameter value of a nonsingular point on the curve, and determine the values of p that might describe the same point
, if it exists, by developing the system of equations below
(5)
From Equation (5), we obtain the two equations below.
(6)
(7)
Clearly, 
and 
are polynomials in p and if Equation (5) is true then, Equations (6) and (7) should have a common Gröbner basis which can be written (Corollary 2.1) as
(8)
By changing the value of 
to
, in Equation (8) we obtain another equation of the form
(9)
which implies that there are two polynomials: 
and 
with a common Gröbner basis.
If Equations (8) and (9) hold, our next task is to evaluate the common Gröbner basis (Corollary 2.2). Let 
denote the common Gröbner basis for 
and
, and 
denotes the common Gröbner basis for 
and
; and according to Corollary 2.2, we will represent 
and 
as 
and 
respectively and also represent the Gröbner basis 
and 
as 
and 
respectively and hence we can write:
(10)
(11)
Equation (3) can be evaluated using Equations (10) and (11), while the values of a, b, c and d must be determined by using the conditions: when
, 
and when
, 
since the endpoint interpolation property must be satisfied by both curves i.e. the properly and improperly parameterized curves.
After obtaining 
and 
our final task is to determine the coefficients of Equation (2) i.e. the properly parameterized rational curve. Let 
and 
have a maximum degree m, and u be the degree of the improperly parameterized rational curve. Hence, the degree of the properly parameterized curve shall be
.
Finally; Equation (2) takes the form
(12)
(13)
(14)
We now use the method of undetermined coefficients [15] to find the coefficients
, 
, and
.
The whole algorithm is summarized as follows:
1) At the beginning we pick 
values of p.
2) We follow the procedures above and compute
.
a) If 
gives a one-to-one relationship between q and p (i.e. properly parameterized) the algorithm will CONTINUE by selecting a new value of p from step 1.
b) If 
doesn’t give a one-to-one relationship between q and p (i.e. improperly parameterized) the algorithm will TERMINATE.
Our algorithm will not terminate at step 2(a) iff the equation 
gives a one-to-one relationship between q and p i.e. properly parameterized; but will terminate at step 2(b) if 
does not give a oneto-one correspondence between q and p i.e. improperly parameterized.
In this paragraph, we would throw light on how the Gröbner basis of an ideal is computed using Buchberger’s algorithm ([10] p. 90, Theorem 2). The uniqueness of the Buchberger algorithm in this paper is that, it gives not only Gröbner basis as is usual but a common Gröbner basis when applied to a 
field. Given a polynomial ideal 
then, the algorithm proceeds as follows:
Input: 
Output: a Gröbner basis 
for I, with 
REPEAT
FOR each pair
, 
in 
DO
IF 
THEN
UNTIL 
At the initial phase of the algorithm, G is enlarge by adding the remainder 
for
. If
, then u, v and 
are also in I and therefore, since we are dividing by
, we obtain
. It is interesting to note that G contains the given basis F of I and as such, G is a real basis of I. The algorithm terminates when
, which means that 
for
.
Finally, it is necessary to note that if the polynomial ideal I is in the 
field, then the above algorithm will give only one Gröbner basis (i.e. common Gröbner basis) that is common to both ideal members.
3. Review of a Numerical Example
In this section we solve a numerical example from [2] using our algorithm to detect improper parameterization.
We consider the rational cubic Bezier curve defined by the equations
and compute the parametric substitution that gives the equations below
We pick 
and
. When
, we have:
The resultant of these two polynomials is:
This means that 
and 
have a common Gröbner basis
. Therefore, the 
of these two polynomials is:
When
, we have:
The resultant of 
and 
is:
This tells us that there is a common Gröbner basis for the two polynomials. Hence, GB4 for the two polynomials is:
Our parametric substitution becomes
We now use the endpoint interpolation property i.e. 
when 
and 
when 
and determine a, b, c and d to compute our parameter. The first condition gives
, and then select 
and
. The second constraint gives
, we choose 
and
, and finally obtain our parameter
.
4. Analysis
In [2], the algorithm uses an assumption for the existence of a common factor for the two polynomials and finally compute this common factor using the concept of the Euclidean algorithm.
In this piece of work, we utilize a necessary and sufficient condition to confirm that the two polynomials have a common Gröbner basis.In Section 3, we see that the existence of common Gröbner basis for both values 
and 
is confirmed by the fact that both 
and 
equals zero. After confirming the existence of a common Gröbner basis the algorithm is then used to compute this common Gröbner basis.
From Section 3, we see also that there is a one-to-two correspondence between parameter values of q and p, i.e. one value of q gives two values of p as it is evident from the obtained parametric relation
; and also the parameterization has a tracing index of two i.e. the curve is doubly traced.Therefore, the curve is improperly parameterized.
5. Conclusions
The algorithm in [2] assumes that there is a common factor for the two polynomials and then uses the notion of the Euclidean algorithm to compute the common factor. However, it is interesting to note that the Euclidean algorithm requires divisibility in the field 
[10]. Our algorithm, first of all, confirms the existence of a common Gröbner basis before any computational attempt is made.
The advantages of our algorithm are as follows: Our algorithm always confirms the existence of a common Gröbner basis before computation. Secondly, it is based on the concepts of Gröbner bases, which requires operations in the field
. We just need to indicate the ordering i.e. lexicographic order, graded lexicographic order, or graded reverse lexicographic order.
Finally, from our algorithm in Section 2, we conclude with no doubt that it is also possible to detect improper parameterization using the notion of Gröbner bases iff the polynomial ideal I is in the 
field.
6. Acknowledgements
The authors would like to thank the anonymous referees for their useful comments on this paper. We would also like to thank the Chinese Scholarship Council.
NOTES