
Proceedings Paper
Floating-point geometry: toward guaranteed geometric computations with approximate arithmeticsFormat | Member Price | Non-Member Price |
---|---|---|
$17.00 | $21.00 |
Paper Abstract
Geometric computations can fail because of inconsistencies due to
floating-point inaccuracy.
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
tolerance ε.
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
available.
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.
Paper Details
Date Published: 3 September 2008
PDF: 12 pages
Proc. SPIE 7074, Advanced Signal Processing Algorithms, Architectures, and Implementations XVIII, 70740M (3 September 2008); doi: 10.1117/12.796597
Published in SPIE Proceedings Vol. 7074:
Advanced Signal Processing Algorithms, Architectures, and Implementations XVIII
Franklin T. Luk, Editor(s)
PDF: 12 pages
Proc. SPIE 7074, Advanced Signal Processing Algorithms, Architectures, and Implementations XVIII, 70740M (3 September 2008); doi: 10.1117/12.796597
Show Author Affiliations
Jean-Claude Bajard, LIRMM (France)
Philippe Langlois, DALI (France)
Dominique Michelucci, LE2I (France)
Philippe Langlois, DALI (France)
Dominique Michelucci, LE2I (France)
Géraldine Morin, INPT (France)
Nathalie Revol, INRIA, Univ. de Lyon (France)
Nathalie Revol, INRIA, Univ. de Lyon (France)
Published in SPIE Proceedings Vol. 7074:
Advanced Signal Processing Algorithms, Architectures, and Implementations XVIII
Franklin T. Luk, Editor(s)
© SPIE. Terms of Use
