Polynomial system solving and computational geometry.
Many algorithms from computer algebra are used in computational geometry such as cylindrical algebraic decomposition for computing the topology of curves. They mostly concern univariate solving (resultants, Sturm sequences, Descartes method, etc.).
In this lecture, the goal is to show that recent algorithms for exact/certified multivariate solving can also be used efficiently in computational geometry after eventually formulating the problem in a different way.
Complete Adaptive Algorithms for Curves and their Analysis
Geometric operations on curves and surfaces can be
based on algebraic techniques (e.g., cylindrical algebraic decomposition, resultants)
or on numerical/geometric techniques
(e.g., subdivision methods, marching cubes).
The latter techniques are practical, adaptive but usually incomplete.
We shall describe some new research to provide adaptive algorithms
for geometric operations that are complete.
In particular, we address the problems of computing intersection of curves
and topologically correct meshing of singular curves.
Another major challenge is the complexity analysis of
such problems. We describe some progress in this direction.