Finite Precision Elementary Geometric Constructions

Olivier Devillers (1) , Philippe Guigue

1 PRISME - Geometry, Algorithms and Robotics

In this paper we propose a new approach for the robust computation of the nearest integer lattice points of some specific geometric constructions (intersection of two planar segments, circumcenter of a planar triangle and of a spatial tethraedron). Given that the data and the final results of the geometric constructions are stored using single precision floating point representation (typically fixed size integers), the proposed algorithms first perform the geometric construction in IEEE double precision floating point arithmetic, the rounding error is estimated, and only if the error estimation indicates that the result of the floating point computation may be wrong, the computation is repeated with exact arithmetic. The basic advantage is that exact computations are in most cases avoided, thus reducing both the storage and the required computation time.

Mots clés: COMPUTATIONAL GEOMETRY; ROBUSTNESS; FLOATING POINT ARITHMETIC; FLOATING POINT FILTER

Domaines: Autre [cs.OH]

Olivier Devillers, Philippe Guigue. Finite Precision Elementary Geometric Constructions. RR-4559, INRIA. 2002. ⟨inria-00072029⟩