The Science behind LEDA, CGAL and EXACUS

The course material consists of the following four papers:

Here are the slides for my lectures:

And here come the Exercises.

The following text gives you some background for my work.

Algorithms are problem solving recipes intended for humans; they are usually expressed in a mixture of natural language, mathematical notation, and programming notation. In contrast, programs are intended for machine execution; they are expressed in a programming language.

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.

Geometric Computing with Curves and Surfaces

Classroom Examples of Robustness Problems in Computational Geometry

The algorithms of computational geometry are designed for a machine model with exact real arithmetic. It is well-known that substituting floating-point arithmetic for the assumed real arithmetic may cause implementations to fail. However, there are no concrete comprehensive examples. There is neither a paper nor a textbook that systematically discusses what can go wrong and provides simple examples for the different 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 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.

Computing with Curves and Surfaces

The simplest curves are conics such as circles, ellipses, parabolas, and hyperbolas. I discuss how to do exact geometric computations with conics.

The paper A Computational Basis for Conic Arcs and Boolean Operations on Conic Polygons appeared in ESA 2002.

The techniques extend to algebraic curves of arbitrary degree ( Eigenwillig, Kerber: Exact and Efficient 2D-Arrangements of Arbitrary Algebraic Curves (SODA 2008)) and also to algebraic surfaces ( Berberich, Kerber, Sagraloff: Geometric Analysis of Algebraic Surfaces Based on Planar Arrangements (SoCG 2008))

Isolating Roots of Real Polynomials, a Key Subroutine

Isolating the real roots of a real polynomial is a key subroutine for the algorithms in the preceding section. We discuss a variant of Descartes method that works for polynomials with real coefficients.

The paper An Exact Descartes Algorithm with Approximate Coefficients appeared in CASC 2005.