Finite Precision Elementary Geometric Constructions

Olivier Devillers 1 Philippe Guigue
1 PRISME - Geometry, Algorithms and Robotics
CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : 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.
Document type :
Reports
Complete list of metadatas

Cited literature [20 references]  Display  Hide  Download

https://hal.inria.fr/inria-00072029
Contributor : Rapport de Recherche Inria <>
Submitted on : Tuesday, May 23, 2006 - 7:36:18 PM
Last modification on : Saturday, January 27, 2018 - 1:31:26 AM
Long-term archiving on : Sunday, April 4, 2010 - 10:49:43 PM

Identifiers

  • HAL Id : inria-00072029, version 1

Collections

Citation

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

Share

Metrics

Record views

304

Files downloads

302