It has been a good tradition of the SIAM conference series on
Geometric Design to organize a minitutorial
on a topic of current interest. Two such minitutorials will be
held at the 10th conference. They will take place at the
same location
on Sunday, November 4, 2007,
immediately preceding the main scientific program of the conference.
ALL PARTICIPANTS OF THE CONFERENCE ARE INVITED TO ATTEND FREE OF CHARGE.
The first minitutorial is scheduled
during the period 10am-12noon, to be given by Bernard Mourrain, while the second
will take place during the slot 2-5pm and will be given by Chris Hoffmann and Meera
Sitharam.
Below are descriptions of both minitutorials.
- The ABC of
Geometric Constraint Solving
Organizers: Christoph M. Hoffmann, Purdue University &
Meera Sitharam, University of Florida
The tutorial will present a birds-eye view of geometric constraint solving,
motivated by applications in engineering and in molecular biology. We will discuss
elementary methods that anyone can implement and advanced questions that are at this
time in the research domain. The following topics will be explored:
A) Applications in engineering and molecular biology; underlying equational problems; sequential vs. simultaneous problems.
B) Basic techniques for bottom-up triangle decomposition; extensions to higher dimensions and to higher-order subproblems; solution space issues.
C) Advanced topics: intrinsic complexity, DR plans, special techniques.
At the end, participants will be ready to implement a simple constraint solver engine and have enough background to fast-track into the literature on the subject.
- Subdivision Methods for the Solution of Non-linear Equations or How to
Cut a Long Story Short.
Organizer: Bernard Mourrain, INRIA, France
Many operations in shape processing reduce to the resolution of
non-linear equations. Among numerous methods which exists for solving
such equations, the subdivision approach appears to be practically
efficient for solving problems which occur in geometric modeling
problems.
The objectives of this tutorial, is to give a comprehensive overview of
such methods based on divide-and-conquer schemes to localize the (real)
solutions of polynomial equations. We will briefly describe the
landscape of polynomial solvers and the family of subdivision solvers
from this perspective.
After this introduction, we will consider solvers of univariate
equations, detail their subdivision strategies and the properties they
exploit to isolate efficiently the real solutions. This tour will bring
us to Descartes rule of sign, De Casteljau algorithm, Continued fraction
expansion, and numerical approximation issues.
The second part will be devoted to multivariate equations. Techniques
which reduce to solving univariate problems will be explained and
analysed.
Preconditioning operations and certification criteria will be detailed
and illustration on practical problems will be given.
Finally, we will consider extensions of this approach to problems where
solution sets are curves or surfaces. We will see how their topology can
be computed from the application of such subdivision techniques,
including the treatement of singular points.
These developments will be illustrated by examples, and experimentation
with a computer algebra system and a geometric modeler software. We plan
to provide a support in order to encourage the audience to do the
experimentation itself.
|