Page 118 - Geometric Modeling and Algebraic Geometry

7

Curve Parametrization over Optimal Field Extensions
Exploiting the Newton Polygon

Tobias Beck and Josef Schicho

Johann Radon Institute for Computational and Applied Mathematics,
Austrian Academy of Sciences
Tobias.Beck@oeaw.ac.at
Josef.Schicho@oeaw.ac.at

Summary. This paper describes an algorithm for rational parametrization of plane algebraic
curves of genus zero. It exploits the shape of the Newton polygon. The computed parametriza-
tion has coefficients in an optimal field extension, which is of degree one or two.

7.1 Introduction

Given a bivariate polynomial f ∈ K[x, y] over a perfect field K (in particular
any field of characteristic zero) we will describe a method to find a proper para-
metrization of the curve defined implicitly by f if it exists. That is we try to
find (X(t),Y (t)) ∈ L(t) with L | K an algebraic field extension such that
2
f(X(t),Y (t)) = 0 and (X(t),Y (t)) induces a birational map from the affine line
to the curve. One condition for the existence of such a parametrization is that f
is absolutely irreducible, i.e. cannot be factored over any algebraic field extension
of K. In case f is absolutely irreducible, existence can be decided by computing a
numerical invariant of the curve, namely its genus. This is the problem of finding
a rational parametrization, a well-studied subject in algebraic geometry. There are
already several algorithms, e.g. [10, 13, 14] and [18].
The complexity of the former algorithms is very sensitive with respect to the
total degree of f.If f is sparse then one can take advantage by exploiting the shape
of its Newton polygon (see remark 3). The algorithm described in [1] is the first to do
so. The main idea there is to adapt an algorithm in [14] for curves in the projective
plane to curves in a toric surface defined by the Newton polygon. In [1] and [14], the
computed parametrizations have coefficients in a field extension of possibly large
degree. On the other hand it is well-known that field extensions of degree at most
2 always suffice, and there are algorithms that compute parametrizations using an
optimal field extension, e.g. [15] and [18].
The original result in this paper is an adaptation of the method described in [18]
to the toric case. This gives a parametrization algorithm producing a parametrization
in an optimal field extension which exploits the shape of the Newton polygon. We