No label defined (Q4945515)

The author gives a survey of techniques that have been proposed and successfully used to attack robustness problems in the implementation of geometric algorithms. This survey is based on precision and robustness in geometric computation [Chapter 9 in Algorithmic Foundations of Geographic Information Systems, Lect. Notes Comput. Sci. 1340, Springer-Verlag (1997)]. It is observed that the precision problems can make implementation of geometric algorithms very unpleasant if appropriate techniques are not used to deal with imprecision [cf. \textit{A. R. Forrest}, in Techniques for Computer Graphics, eds. \textit{D. F. Rogers} and \textit{R. A. Earnshaw}, Springer-Verlag (1987; Zbl 0619.68076), pp. 23-37 and \textit{K. Mehlhorn} and \textit{S. Nähar}, Proc. 13th. World Computer Congress, IFIP94, 1, 223-231 (1994; Zbl 0619.68076)]. Following concluding observations are also made in the paper. Although appreciable progress has been made to the study of precision and robust problems, but no satisfactory general-purpose solution has been found. If exact predicates are available, exact geometric computation is a more convenient approach. Exact computation is a prerequisite for the use of symbolic perturbation schemes. A few references to related surveys are also indicated [eg. \textit{C. K. Yap}, Comput. Geom. 7, No.~1-2, 3-23 (1997; Zbl 0869.68104)]. For the entire collection see [Zbl 0930.65001].