Classroom Examples of Robustness Problems
in Geometric Computations

Lutz Kettner, Kurt Mehlhorn, Sylvain Pion, Stefan Schirra, and Chee Yap


Table of
Contents


Introduction

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 work, 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. We include selected talks and teaching material, also of related topics, for your convenience and we invite you to use it in your classes.


Selected Publications

1

Classroom Examples of Robustness Problems in Geometric Computations. Lutz Kettner, Kurt Mehlhorn, Sylvain Pion, Stefan Schirra, and Chee Yap. 25 pages. Submitted. 2006. [Abstract] [PDF Preprint] [PostScript Preprint]

2
____

Classroom Examples of Robustness Problems in Geometric Computations. Lutz Kettner, Kurt Mehlhorn, Sylvain Pion, Stefan Schirra, and Chee Yap. In: Proc. of the 12th Annu. European Sympos. Algorithms (ESA'04), Bergen, Norway. LNCS 3221, Springer, pp. 702-713, September, 2004. © Springer-Verlag [Abstract] [PDF] [PostScript]


Selected Talks and Course Materials

1
____

Classroom Examples of Robustness Problems in Geometric Computations. 12th Annu. European Sympos. Algorithms (ESA'04), Bergen, Norway. September, 2004. [PDF] [PPT]

2

Classroom Examples of Robustness Problems in Geometric Computations. Lecture in the course on Algorithm Engineering, by Kurt Mehlhorn, Lutz Kettner and Uli Meyer in Saarbrücken University and University Kaiserslautern, March 2005. [PDF] [PPT]

3

Robust Geometric Computation. Lecture in the course on Algorithm Engineering, by Kurt Mehlhorn, Lutz Kettner and Uli Meyer in Saarbrücken University and University Kaiserslautern, March 2005. [PDF]

4

Controlled Perturbation for Delaunay Triangulations. Lecture in the course on Algorithm Engineering, by Kurt Mehlhorn, Lutz Kettner and Uli Meyer in Saarbrücken University and University Kaiserslautern, March 2005. [PDF]


Download of Software, Data Sets, and Figures

Release 2006: Corresponding to Journal Version [1]

Release 2004: Corresponding to ESA Conference Version [2]


Links


Lutz Kettner (<surname>@mpi-inf.mpg.de). Last modified on Thursday, 08-Mar-2007 09:09:45 MET.