Graphics Reference
In-Depth Information
Solution.
Clearly, the curve is just the set
(
)
=
4
3
2
()
Vt
---
xt
,
yt
,
z
VI
,
where I is the ideal <t
4
- x,t
3
- y, t
2
- z> in
C
[t,x,y,z]. One can show that
{
}
2
2
2
2
3
G
=- +
t
z ty
,
-
z
,
tz
-
y x
,
-
z
,
y
-
z
is a Gröbner basis for I using the lex order of
C
[t,x,y,z] with z < y < x < t. Note how
the last two polynomials in G do not involve the parameter t. It follows that the curve
is contained in the variety defined by
2
xz
yz
-=
-=
0
0.
23
Does this variety in
C
3
contain any extra points that were not in the curve? It turns
out the answer to this question is no. See Theorem 10.11.4 and the comments leading
up to it. We were again able to solve our problem with Gröbner bases. The general
algorithm for the implicitization problem using this approach is described in the next
section.
In this section we have seen how useful Gröbner bases can be. It is therefore
important to have the most efficient algorithm for computing them possible. We have
indicated a few improvements to the basic Buchberger algorithm. More improvements
can be made by a careful analysis of the role that S-polynomials play in the algorithm.
We refer the reader to [AdaL94] or [CoLO97] for a discussion of such improvements
and actual algorithms that carry them out. Even so, finding Gröbner bases can still
be a very slow process for certain ideals. From a theoretical point, it is a very complex
problem for the worst cases. One problem is that the degrees of the polynomials in
a Gröbner basis can be quite large. It has been shown that even if an ideal can be
generated by polynomials whose total degree is bounded by some d, the degrees of
the polynomials in a Gröbner bases for it can in certain cases be doubly exponential
in d. Initial pessimism in this regard has been mitigated by the fact that things do not
turn out so badly in many practical problems. Recall our pointing out that the mono-
mial order we choose and the way we order the individual variables X
i
can influence
the results. One has found that the degrevlex order seems to work best in most
instances in that one seems to get polynomials of smallest total degree. Nevertheless,
although Gröbner bases have a great theoretical value and have much going for them,
it turns out that methods based on resultants turn out to be more efficient in many
practical problems. Sweeping statements that one method is always better than the
other are not possible.
The implicitization problem remains a difficult computational problem in general.
The solution can end up being a high degree polynomial with a large number of terms.
For example, in CAGD a triangular surface patch of degree n has an implicit equa-
tion of degree n
2
in general. A tensor product patch using polynomials of degree n
and m has an implicit equation of degree 2nm in general. See [Sede87]. For another
approach to implicitization using the Wu-Ritt method see [Hoff93] or [CoLO97].
