Floating-point geometry: toward guaranteed geometric computations with approximate arithmetics

Jean-Claude Bajard; Philippe Langlois; Dominique Michelucci; Géraldine Morin; Nathalie Revol

doi:10.1117/12.796597

3 September 2008 Floating-point geometry: toward guaranteed geometric computations with approximate arithmetics

Jean-Claude Bajard, Philippe Langlois, Dominique Michelucci, Géraldine Morin, Nathalie Revol

Proceedings Volume 7074, Advanced Signal Processing Algorithms, Architectures, and Implementations XVIII; 70740M (2008) https://doi.org/10.1117/12.796597
Event: Optical Engineering + Applications, 2008, San Diego, California, United States

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.

Citation Download Citation

Jean-Claude Bajard, Philippe Langlois, Dominique Michelucci, Géraldine Morin, and Nathalie Revol "Floating-point geometry: toward guaranteed geometric computations with approximate arithmetics", Proc. SPIE 7074, Advanced Signal Processing Algorithms, Architectures, and Implementations XVIII, 70740M (3 September 2008); https://doi.org/10.1117/12.796597

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available

Members: $17.00

Non-members: $21.00 ADD TO CART

PROCEEDINGS
12 PAGES

DOWNLOAD PAPER SAVE TO MY LIBRARY

GET CITATION

RIGHTS & PERMISSIONS

Get copyright permission Get copyright permission on Copyright Marketplace

KEYWORDS

Tolerancing

3D modeling

Computing systems

Algorithm development

Solids

Statistical modeling

Clouds

Show All Keywords

Keywords/Phrases

Search In:

Publication Years