Classroom Examples of Robustness Problems in Geometric Computations. Lutz Kettner, Kurt Mehlhorn, Sylvain Pion, Stefan Schirra, and Chee Yap. Technical Report ECG-TR-363100-01, Max-Planck-Institut für Informatik, INRIA Sophia-Antipolis, 2004.
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 an incremental planar convex hull algorithm and give examples which make the algorithm fail in many different ways. For this algorithm our examples cover the negation space of the correctness properties of the algorithm. 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 the paper will be useful for teaching computational geometry. The paper comes with a companion web-page http://www.mpi-inf.mpg.de/~kettner/proj/NonRobust/.
[PDF]
[PostScript]
[--> Conference
Version]
[Project Page]