Page 147 - Geometric Modeling and Algebraic Geometry

148 F. Cazals et al.
8.3.1 Algebraic tools

Two algebraic methods are ubiquitously called by our algorithm: univariate root iso-
lation and rational univariate representation. We briefly present these tools and give
references for the interested reader.
Univariate root isolation. This tool enables to isolate roots of univariate poly-
nomials whose coefficients are rational numbers, by means of intervals with rational
bounds. The method uses the Descartes rule and is fully explained in [20].
Rational univariate representation [19]. The Rational Univariate Representa-
tion is, with the end-user point of view, the simplest way for representing symboli-
cally the roots of a zero-dimensional system without loosing information (multiplic-
ities or real roots) since one can get all the information on the roots of the system by
solving univariate polynomials.
Given a zero-dimensional system

I =<p 1 ,...,p s >

where the p i ∈ Q[X 1 ,...,X n ], a Rational Univariate Representation of V(I), has
the following shape:

(T) g t,X n (T)
f t (T)=0,X 1 = g t,X 1 ,...,X n = ,
g t,1 (T) g t,1 (T)
∈ Q[T] (T is a new variable). It is uniquely defined
,...,g t,X n
where f t ,g t,1 ,g t,X 1
w.r.t. a given polynomial t which separates V (I) (injective on V (I)), the polynomial
f t being necessarily the characteristic polynomial of m t in Q[X 1 ,...,X n ]/I. The
RUR defines a one-to-one map between the roots of I and those of f t preserving the
multiplicities and the real roots:
V(I)(∩R) ≈ V(f t )(∩R)
α =(α 1 ,...,α n ) → t(α)
( g t,X 1 (t(α)) ,..., g t,X n (t(α)) ) ← t(α)
g t,1 (t(α)) g t,1 (t(α))
The RUR also enables efficient evaluation of the sign of polynomials at the roots of
a system.

8.3.2 Assumptions on the ridge curve and study points

According to the structure of the singularities of the ridge curve recalled in section
8.2, the only assumption made is that the surface admits generic ridges in the sense
that real singularities of P satisfy the following conditions:
• Real singularities of P are of multiplicity at most 3.
• Real singularities of multiplicity 2 are called purple points. They satisfy the sys-
tem S p = {a = b = a = b =0,δ(P 2 ) > 0,p 2 =0}. In addition, this implies

that two real branches of P are passing through a purple point.