Research report 2011 - Max Planck Institute for Informatics
Exact Geometric Computing
Algorithmen und Komplexität (Kurt Mehlhorn)
SummaryThe 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.