Computer systems for algebraic geometry aim at exact solutions and consequently dominantly use exact arithmetic. CAD-systems are based on double precision floating point representation and allow the user to provide geometric tolerances defining when two points should be considered to be the same, and when curves or surfaces should be considered to be completely or partial coincident. Consequently when two surfaces are closer than the geometry tolerance and intersecting in a complex curve topology, the CAD-users in some cases expect an area of coincidence to be reported rather than the correct intersection topology. Similarly if no exact intersection exists but the surfaces are closer than the specified tolerances the CAD-user will expect the surfaces to be reported as partial coincident with a description of the area of coincidence. In other circumstances the CAD-user expects the exact solution to be found.

In the last years INRIA has exploited the use of floating point calculations as part of algorithms for the calculation of a certified topology for the intersection and self-intersection of exactly represented surfaces. SINTEF has continuously extended the use of certification in their implementation of surface intersection and self-intersection algorithms for the CAD-industry.

We will investigate the approaches for the certification of tolerance dependent intersection and self-intersection algorithms within algebraic geometry and CAD-type geometry in order to develop new approaches for the result certification for improved quality and performance of intersection algorithms.

For more details contact: