Floating-point arithmetic is widely used because it has many practical advantages. It provides a familiar approximation to the real numbers, with useful properties like automatic scaling. It is widely available on different computers and is well supported by programming languages. Current workstations have highly optimized native floating-point arithmetic, sometimes faster than native integer arithmetic. Floating-point arithmetic is sufficiently widespread in scientific computing that programmers rarely consider other options.
However, some geometric predicates cannot be resolved using floating-point arithmetic. If an instance of a predicate is nearly degenerate, then the value of the corresponding expression can be very small, less than the rounding error in the floating-point evaluation of the expression. Hence the sign of the computed expression may well be erroneous. Usually it is possible to argue that the computed expression value is the true value for slightly perturbed coordinate data. Since coordinate data may well be imprecise originally, the erroneous sign may appear to be innocuous. The difficulty arises with multiple predicate evaluations; there is no guarantee that any single global perturbation produces all the computed predicate values. Indeed, the computed predicate values may be geometrically inconsistent. Catastrophic implementation failure can easily result.
There are two broad categories of methods to deal consistently with floating-point rounding error. One category formalizes the notion of tolerances. A typical strategy might associate inner and outer tolerances with an object, say a point. If the inner tolerances of two points intersect, they are deemed coincident and merged; if the outer tolerances are disjoint, they are deemed separate; if neither case holds, the situation is ambiguous. As long as no ambiguity results during a computation, the result is correct. The hope is that ambiguities arise infrequently; an obvious drawback of this strategy is that is not clear what to do if an ambiguity does arise. Another drawback is that the generalization to complex geometric objects is not straightforward.
Since arithmetic operations have non-constant costs,
it makes sense to judge the performance of an algorithm
in terms of the precision needed in the output of the
algorithm. This gives rise to the notion of ``precision-sensitive
algorithms'' where the running time is a function of
as well
as a function of the input size. Since
can be exponential
in the input size, exploiting this new parameter can be
quite significant. Notice that precision-sensitivity is
the bit-complexity analogue of the very fruitful idea of
``output-sensitivity'' invented by CG. The paper
[35] first applied this concept to the NP-hard problem
of Euclidean shortest paths.
A second floating-point approach is error analysis. This approach is modeled on the error analysis of numerical methods, particularly linear algebra. The goal is to show that a suitably implemented algorithm provides an answer that is in some precise sense near the mathematically correct answer. Error analysis of geometric algorithms requires consideration of both combinatorial and numeric structure. Often it is easy to argue that an algorithm produces combinatorially valid output, at least with suitably relaxed requirements. It has turned out to be much more difficult to argue that the numeric error associated with combinatorial structure is small. Full error analysis has been carried only for a few simple algorithms.