hide
Free keywords:
-
Abstract:
The algorithms of computational geometry are designed for a machine model with
exact real arithmetic. Substituting floating-point arithmetic for the assumed
real arithmetic may cause implementations to fail. Although this is well known,
it is not common knowledge. There is no paper that systematically discusses
what can go wrong and provides simple examples for the di.erent ways in which
floating-point implementations can fail. Due to this lack of examples,
instructors of computational geometry have little material for demonstrating
the inadequacy of floating-point arithmetic for geometric computations,
students of computational geometry and implementers of geometric algorithms
still underestimate the seriousness of the problem, and researchers in our and
neighboring disciplines still believe that simple approaches are able to
overcome the problem. In this paper, we study simple algorithms for two simple
geometric problems, namely computing convex hulls and triangulations of point
sets, and show how they can fail and explain why they fail when executed with
floating-point arithmetic.
