Research report 2011 - Max Planck Institute for Informatics

Exact Geometric Computing

Sagraloff, Michael
Algorithmen und Komplexität (Kurt Mehlhorn)
The research group focuses on the development of exact and complete methods to handle complex geometric objects which are fundamental for many geometric algorithms. There exist powerful methods from Algebra to solve the considered problems in theory, however, they turn out to be non-practical because of the high computational cost for the needed symbolic operations. By combining techniques from different mathematical fields, we have been able to develop efficient algorithms which only use a minimum of symbolic operations, whereas most operations are based on fast approximate arithmetic.

For the full text, see the German version.

Go to Editor View