2.8 Robustness

Non-robustness refers to two notions. First, the result may not be correct (for instance, the convex hull of a set of points is not convex). Then, the program stops during the execution with an error or in a more catastrophic way (the program fails) with an overflow, an underflow, a division by zero, an infinite loop, etc. If the algorithm is reputed to be error-free (from a mathematical point of view), this means that its implementation leads to an erroneous behavior. Anyone who has implemented a geometric algorithm is likely to have faced this type of problem at some point.

This section has several aims. First, we give a very brief overview of the potential reasons why numeric problems arise; we recall how real numbers are encoded on most computers, and explain why the issues are even more difficult in a geometric context. We then provide some guidelines to reduce these risks, and finally we give an overview of the state-of-the-art techniques used to make floating-point operations robust.