- Classroom Examples of Robustness Problems in Computational Geometry
- Controlled Perturbation for Delaunay Triangulations
- A Computational Basis for Conic Arcs and Boolean Operations on Conic Polygons
- An Exact Descartes Algorithm with Approximate Coefficients

- Introduction
- Classroom Examples
- Controlled Perturbation
- Conic Polygons
- A Descartes Algorithm for Polygons with Approximate Coefficients
- Certifying Algorithms

Algorithmicists design algorithms. The success criteria are correctness, elegance, and small asymptotic running time.

Applications need programs. The success criteria are correctness, versatility, fit into an environment, and actual running time on actual instances.

I will discuss the relationship of algorithms and programs along three axes:

How do we go from a correct algorithm to a correct program? Programming is an error-prone task and it is a highly non-trivial task to convert a correct algorithm into a correct program. We advocate certifying programs as a pragmatic approach to program correctness. On an input x, a certifying algorithm for a function f does not only return y, the alleged function value f(x), but also a certificate (proof, convincing evidence) of the equality ``y = f(x)''. In this way, a user of the program can convince himself that the program worked correctly on the given input x.

The correct implementation of geometric algorithms is particularly difficult, because geometric algorithms are usually designed for inputs in general position and for the Real-RAM model of computation. I give examples, how miserably naive implementations can fail, show how to realize a Real-RAM as needed for computational geometry, discuss approaches to overcome the general position problem, and finally come to exact algorithms for curves and surfaces.

Algorithm engineering is the scientific approach to making algorithms and the corresponding programs fast. It will be the subject of my third lecture.

The background for my lectures is the experience with LEDA, CGAL, and EXACUS.

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 have to learn about the seriousness of robustness problems by experiencing the difficulties while programming. In this paper, we provide a case study of what can go wrong and why with geometric algorithms when executed with floating-point arithmetic naively. For our study, we have chosen two simple algorithms which are often taught, an algorithm for computing convex hulls in the plane and an algorithm to compute Delaunay triangulations in space. A preliminary version of this paper appeared at ESA 2004. The full paper will appear in Computational Geometry Theory and Applications.