Arithmetic for geometric computing

A problem of accuracy

The floating point computation performed by standard computers is not exact, but rounded off. The numerical result of a computation is in general close to the true result, but often not equal.

If a numerical result is sought, these imprecisions are usually acceptable. If a logical decision has to be taken based on this result (for example based on the sign of the result), the decision will be right in most cases but may be wrong (if the value is close to zero, its sign is not guaranteed to be correct). The consequences of taking a wrong decision can be fatal to the algorithm.

For instance: computing the orientation of a triangle

Three points p,q,r define a clockwise, counter-clockwise triangle, or may be aligned. These three cases correspond to a positive, negative, or null value of the following determinant:


Rounding off leads to the wrong orientation

Suppose our computer computes in base 10, but only keeps the two most significant digits. We call this fixed precision computation.

Let us take three points:

  • p = (-94,0)
  • q = (92,68)
  • r = (400,180)
The true value of the determinant is
Our fixed precision computer will give, however,

Triangle pqr is oriented clockwise, but our computer is lead to the opposite conclusion because it rounds off the computation. Errors such as this can lead to inconsistencies. Mathematically, if triangles pqt, qrt et rpt are oriented counter-clockwise, then triangle pqr is also oriented counter-clockwise.

This kind of mathematical theorem can be invalidated by fixed precision computations, because of round-off errors.

Floating point computation is not that bad

As we have seen, fixed precision computation can lead to inconsistent results. Fortunately, it does not happen too often. Specifically, it only happens when the result of a fixed precision computation is small enough.

Shown on the right is a curve that gives the probability that the computed value of the determinant is smaller that A, for three points p,q,r picked uniformly at random in a unit circle.

This kind of result can be used to show that, when we compute the orientation as above on a computer that uses standard double precision, the answer will be incorrect with a probability smaller that tex2html_wrap_inline8

Exact computation is possible

We need to notice that finding the exact of the orientation predicate, or any other predicate, does not mean compute exactly the determinant but just be sure of its sign.

When the rounded computed value is large enough to certify its sign, the rounded result can be used.

If the computed value is to close from zero, something else is needed. The rounded arithmetic is used to filter difficult cases.

In these difficult cases, an exact computation must be done, either using an exact arithmetic library, either through a geometric method.

Arithmetic filters

To be sure that the computed sign is exact, we must precise what "large enough" means in the previous paragraph.

Thus, the computation of our determinant must be done with a rigorous error computation to allow to certify the computed sign. Depending on the error computation method, we will speak about

Geometrical exact computations

We developed such a method: in order to know the orientation of a triangle pqr in the difficult case when tex2html_wrap_inline8 we translate r by an integral multiple of qp to yield a point r' such that tex2html_wrap_inline10 This translation does not change the orientation and the new determinant is easier to compute.

To know more about it...

Exact computation can be avoided

Another way around these problems is to avoid using the mathematical theorems such as mentioned above.

In general, such algorithms replace the intrinsic consistency implied by the underlying mathematics by explicitly checking and maintaining this consistency.

To know more about.

Un survey talk.

Last modified: Mon Aug 28 10:31:39 MET DST 2000 Olivier Devillers Topics PRISME Homepage la même page en français