A general approach to the analysis of controlled perturbation algorithms (Q654290)

The implementation of a clear geometric algorithm always has to solve the following problem: On the one hand, computing with rounded arithmetic may question the reliability of programs while, on the other hand, computing with exact arithmetic may be too expensive and hence inefficient. One possible solution has been proposed in the recent past years: the implementation of controlled perturbation algorithms which combine the speed of floating-point arithmetic with a protection mechanism that guarantees reliability, nonetheless. In the paper under review the authors present a general methodology for analyzing controlled perturbation algorithms considering the perturbation amount, the arithmetic precision, the range of input values, and the number of input objects. Some examples are studied in detail: the distinctness of points, the 2D-orientation predicate, the orientation test in D-space and the common intersection point of three circles in the plane. The methodology is powerful enough to analyze all geometric predicates that are formulated as signs of polynomials. Nevertheless, in a future work the authors want to extend the analysis from polynomials to rational functions or expressions involving square roots, or to make controlled perturbation applicable not just to sets of points, but to problems whose input has a combinatorial structure.