Geometric computations can fail because of inconsistencies due to
For instance, the computed intersection point between two curves does not
lie on the curves:
it is unavoidable when the intersection point coordinates are non rational,
and thus not representable using floating-point arithmetic.
A popular heuristic approach tests equalities and nullities up to a
But transitivity of equality is lost: we can have A approx B and B approx C,
but A not approx C (where A approx B means ||A - B|| < ε for
A,B two floating-point values).
Interval arithmetic is another, self-validated, alternative; the difficulty
is to limit the swell of the width of intervals
with computations. Unfortunately interval arithmetic cannot
decide equality nor nullity,
even in cases where it is decidable by other means.
A new approach,
developed in this paper,
consists in modifying the geometric problems and algorithms, to
account for the undecidability of
the equality test and unavoidable inaccuracy. In particular, all curves come
with a non-zero thickness,
so two curves (generically) cut in a region with non-zero area, an inner and
outer representation of which is computable.
This last approach no more assumes that an equality or nullity test is
The question which arises is: which geometric problems can still be solved
with this last approach, and which cannot?
This paper begins with the description of some cases where every known
arithmetic fails in practice.
Then, for each arithmetic, some properties of the problems they can
solve are given.
We end this work by proposing the bases of a new approach which aims
to fulfill the geometric computations requirements.