Page 24 - Geometric Modeling and Algebraic Geometry

18 T. Dokken
Sturm-Habicht sequences here supply an exact number of real roots in the inter-
val of interest.
• Finding values in the second parameter direction.Then for each α i i =
1,...,r we compute the real roots of f(α i ,t), β i,j , j =1,...,s i ,. For every
α i and β i,j compute the number of half branches to the right and left of the point
(α i ,β i,j ).
• Reconstruction of topology of the algebraic curve. From the above information
the topology of the algebraic curve in the domain of interest can be constructed.
Papers on this approach in the project are [4, 10, 28, 29, 31].
To ensure the approach to work the root computation has to use extended preci-
sion to ensure that we reproduce the number of roots predicted by the Sturm-Habicht
sequences. The algorithms have been developed using symbolic packages.

1.8 New applications of the approach of approximate
implicitization

A number of different applications of approximated implicitization are addressed in
the subsections following.

1.8.1 Closest point foot point calculations
Inspired by approximate implicitization this problem has been addressed by mod-
eling moving surfaces normal to the surface and intersecting in constant parameter
lines [57]. The set up of the problems follows the ideas of approximate impliciti-
zation; singular value decomposition is used to find the coefficients of the moving
surfaces. By inserting the coordinates of a point into such a moving surface a poly-
nomial equation in one variable results. The zeros of this identify constant parameter
lines with a foot point. Further a theory addressing the algebraic and parametric de-
gree of the moving surface is established.

1.8.2 Constraint solving

Multiple constraints described by parametric curves, surfaces or hypersurfaces over
a domain used for optimization can be modeled using approximate implicitization as
a piecewise algebraic curve, or surface, or hypersurface. Thus a very compact way
of modeling constraints has been identified.

1.8.3 Robotics

Within robotics we have identified a number of uses. We have experimented with
checking for self-intersection of robot tracks. CAD-surfaces used in robot planning
can check for self-intersections by the GAIA tools. The control of advanced robots
can be expressed as systems of polynomial equations. To solve such equations the