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
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.