ABSTRACT
The decisions and the output of a geometric algorithm depend on geometric predicates and on the computation of new and intermediate geometric objects. Geometric computation has two components: a numerical part and a combinatorial part. Many geometric algorithms behave well if the given objects are assumed to be in general position. For example, a set of points in the plane is in general position if no three points are colinear and no four points are cocircular. Non-general positions are also denoted as degeneracy. This chapter discusses the influence of degeneracy and shows how to deal with degeneracy. Robustness guarantees that the output of the algorithm is correct for some perturbation of the input. The algorithm is stable if the perturbation is small. Geometric algorithms are designed under the assumption of the Real Random Access Machine (Real RAM) computer model, which includes exact arithmetic on real numbers and allows a computer-independent analysis of complexity and running time in the famous O-notation.
