Classroom Examples of Robustness Problems in Geometric Computations. Lutz Kettner, Kurt Mehlhorn, Sylvain Pion, Stefan Schirra, and Chee Yap. 25 pages. Submitted. 2006.
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, there is no comprehensive documentation of what can go wrong and why. In this paper, we study simple algorithms for planar convex hulls and 3d Delaunay triangulations and give examples that make the algorithms fail in many different ways. For the incremental planar convex hull algorithm our examples cover the negation space of the correctness properties of the algorithms. We also show how to construct failure-examples semi-systematically and discuss the geometry of the floating-point implementation of the orientation predicate. We hope that our work will be useful for teaching computational geometry.
[PDF Preprint]
[PostScript Preprint]
[Accompanying data and source code]