Page 200 - Geometric Modeling and Algebraic Geometry

11 Subdivision Methods for the Topology of 2d and 3d Implicit Curves 203
The theorem 1 enables a simple yet efficient test of the existence of real roots in
a given domain. This test is essential to our algorithm, as it serves as a key criterion
to classify whether a domain has certified topology, without actually computing the
curve. This allow the our algorithm to execute in reasonably short time, as demon-
strated in our experiments.

11.2.2 Generalization to the multivariate case
The univariate Bernstein basis representation can be generalized to multivariate ones.
Briefly speaking, we can rewrite the definition (Eq. (11.1)) in the form of tensor prod-
n
ucts. Suppose for x =(x 0 , ..., x n−1 ) ∈ R , f =(x) ∈ K[x] having the maximum
degree d =(d 0 , ..., d n−1 ) has the form:

d n

d 0
f(x)= ... b k 1 ,...,k n B (x 0 )...B (x n ) (11.6)
d 0
d 0
k n
k 0
k 0 =0 k n =0
For a polynomial of n variables, the coefficients can be viewed as a tensor of dimen-
sion n.
The de Casteljau subdivision for the multivariate case proceeds similarly to the
univariate one, since the subdivision can be done independently with regards to a
particular variable x i .
Based on these properties, a subdivision solver which can be seen as an improve-
ment of the Interval Projected Polyhedron algorithm in [18], is described in [14]. It
uses the following operations: The multivariate functions to be solved are enclosed
in-between two univariate functions, for each variable. For this purpose, the Bern-
stein control points of the functions are projected in each direction and the upper and
lower envelop are used to define these enveloping univariate polynomials. A lower
and upper approximation of the roots of these univariate polynomials are used to
reduce the domain. If the reduction is not sufficient, the domain is split. These reduc-
tion operations are improved by pre-conditioning steps. See [14] for more details.

11.3 Algorithmic ingredients

We consider the problem of computing the topology of the curve, denoted here-
after as C, resulting from the intersection of two known algebraic surfaces, namely,
f(x)=0 and g(x)=0 defined in R , with f, g ∈ R[x, y, z]. Our discussion is
3
confined to the case where f and g has no common divisor other than 1, so that
their intersection has dimension of 1. We assume moreover that (f, g) is radical or
equivalently that the resultant of f(x, y, z),g(x, y, z) with respect to z after a generic
change of coordinates, is square free.