Symbolic-numeric methods for algebraic curves and surfaces
Bernard Mourrain
GALAAD, INRIA Sophia-Antipolis
Motivation
Algebraic curves and surfaces are involved in many application
domains, ranging from Computer Aided Design up to molecular biology,
robotics... The encountered problems require to solve numeric,
arithmetic, algebraic, geometric, algorithmic questions. In this
tutorial, we will give an introduction to several methods, which can
be used for handling efficiently some of the above questions.
Outline
We will first concentrate on one-dimensional questions such as
isolating the roots of a univariate polynomial, comparing algebraic
numbers, deciding the sign of an algebraic expression which appear for
instance in ray-shooting or sorting points problems.
In a second part, we will consider problems involving points in higher
dimension, and which are related to solving zero-dimensional systems
of polynomial equations. We will give a brief overview of different
approaches for tackling this question, including subdivision,
homotopic, algebraic, and projection methods. We will detail, in
particular, methods based on normal form computations which reduce the
solving question to eigencomputations, extension of Weierstrass-like
methods to the multivariate case, subdivision techniques, based on
representation in the Bernstein basis. A special attention will be
given to projection methods, which can be used to treat efficiently
geometric operations on parametric curves or surfaces, such as
intersection, implicitisation... Applications to the computation
with Steiner surfaces will be shown.
Finally, we will consider combinations of these tools for the
manipulation of algebraic curves and surfaces, such as computing
intersections points or curves, the topology of implicit curves and
surfaces, the arrangement of geometric objects...
This presentation will be illustrated by practical examples, pictures,
and how-to-use hints with the software environment SYNAPS, devoted to
symbolic and numeric applications.
