9.6. Imprecise Arithmetic Approach

Up to now, we tried to solve or avoid the existing problems of robustness and degeneracy for a class of geometric algorithms that are designed and analyzed in the unrealistic model of the Real RAM. Now, we turn to a completely different approach. We consider algorithms that are designed and analyzed under the presence of imprecise predicates. This means that classic results of computational geometry, such as the computation of convex hulls or Delaunay triangulations, must be reconsidered. It seems that we have to reinvent computational geometry results completely. This is the main disadvantage of the given idea.

First, we need a general framework for the use of imprecise or approximative predicates. Then we will present a classical problem solved with approximative predicates; see Section 9.6.2.

Approximative algorithms with approximative predicates in computational geometry can be found, for example, in [Fortune 92a], [Fortune 89], [Guibas et al. 93], and [Fortune and Milenkovic 91].

9.6.1. Epsilon Arithmetic and Approximative Predicates

Epsilon arithmetic ( - arithmetic) is defined in a very general sense: -arithmetic is erroneous, but the errors have to be within a guaranteed error range depending on . The formal definition does not specify the implementation of arithmetic operations. It is easy to see that floating-point arithmetic fulfills the definition of - arithmetic.

Definition 9.38. ( - arithmetic.) -arithmetic consists of at least the arithmetic operations , , and , within a definition range R . The following properties hold:

ˆ x, y ˆˆ R there is a < such that ( x y ) = ( x + y )(1 + ) for < ;
Comparisons <, ‰ , = , ‰ , and > are evaluated exactly.

-arithmetic guarantees a relative error smaller than . For example, floatingpoint arithmetic guarantees a relative error smaller than the corresponding machine epsilon; see Section 9.3.1.

- arithmetic evokes approximative predicates; the sign of the predicate cannot be guaranteed. The weak predicates are defined similar to formal robustness and formal degeneracy; see Definition 9.3 and Definition 9.31.

Definition 9.39. (Approximative predicate.) Let p be a predicate in ^nd . That is, p is a mapping p : ^nd B where B represents the Boolean space {TRUE, FALSE}. is defined to be an approximative predicate iff

p ( x ) implies ( x ), and
( x ) implies that there is an instance x near to x with p ( x ).

A geometric predicate usually comes along with a disjoint counterpart predicate. For example, the orientation test O2D( p ₁ , p ₂ , p ₃ ) for three points p ₁ , p ₂ , and p ₃ in 2D is positive (or TRUE) if and only if the test O2D( p ₁ , p ₃ , p ₂ ) is negative (or FALSE). The two predicates coincidence only for three points on a line. The line l ( p ₁ , p ₂ ) passing through p ₁ and p ₂ separates the plane into two half-planes. Let < . If p ₃ lies above l ( p ₁ , p ₂ ), O2D( p ₁ , p ₂ , p ₃ ) is TRUE. If p ₃ lies below l ( p ₁ , p ₂ ), O2D( p ₁ , p ₃ , p ₂ ) is TRUE.

On the other hand, for two approximative predicates that interact in the sense indicated above, we will not be able to detect the line between them exactly. They will overlap for a bigger set of points. We illustrate this behavior in Figure 9.21. Assume that ( x ) is TRUE for all x above the curve C _p and ( x ) is TRUE for all x below the curve C _q , and the line between the predicates p and q runs between the two curves and cannot be detected exactly. An implementation of one of the two predicates should take care that for all points x within the uncertain area either ( x ) = TRUE or ( x ) = TRUE holds. Altogether, an approximative predicate has to be implemented for both predicates as follows .

Figure 9.21: Two interactive approximative predicates overlap within a region.

Definition 9.40. ( - arithmetic test.) Let and be two approximative predicates. An -arithmetic test for and is a Boolean program CodeP( x ) such that

CodeP( x ) = TRUE ( x ),
CodeP( x ) = FALSE ( x ).

Definition 9.40 means that the implementation of an approximative predicate takes care of its counterpart and always results in TRUE or FALSE. Note that some implementations make use of the third status UNCERTAIN, where the two approximative predicates really overlap and both predicates result in TRUE or FALSE, respectively.

In the next sections, we will present an example of an - arithmetic test for approximative orientation test. An approximative incircle test predicate can be found in [Fortune 92a].

9.6.2. Computing the Convex Hull

We want to design an -arithmetic test for the approximative orientation test predicate and introduce some notions from [Fortune 89].

For three points a , b , and c in the plane, let ˆ ( a, b, c ) denote the range between and spanned counterclockwise from to ; see Figure 9.22. The measure