WORKSHOP ON ROBUST SHAPE OPERATIONS

26 - 28, September, 2007
INRIA Sophia Antipolis

GDR-IM  
 
 

  Home
 
  Invited talks
     Fabrice Rouillier
     Chee Yap
  
  Call for talks
 
  Program
 
  Registration
 
  Participants
 
  Accommodation
 
  Informations
 
  Organization
 
 

 


Invited talks

Fabrice Rouillier

Polynomial system solving and computational geometry.

Abstract :
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.


 Chee Yap

Complete Adaptive Algorithms for Curves and their Analysis

Abstract:
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.